RemoveDuplicatesFromSortedList [source code]

public class RemoveDuplicatesFromSortedList {
static

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode res = head;
        while (head != null && head.next != null) {
            ListNode end = head;
            while (end.next != null && end.val == end.next.val) end = end.next;
            head.next = end.next;
            end.next = null;
            if (head.next == null) break;
            else head = head.next;
        }
        return res;
    }
}

    public static void main(String[] args) {
        RemoveDuplicatesFromSortedList.Solution tester = new RemoveDuplicatesFromSortedList.Solution();
    }
}

delete in linked list这个是一个梗了, 前面已经吃过一次亏了. 关键点就是用 modify 来代替delete;

因为这一题是 sorted, 所以最后的duplicate 都是连在一起的. 两个连在一起的 duplicate, 你要想好应该删哪一个. 更广义的来说, 当有很长的 duplicate 的时候, 你是要删除previous duplicates还是later duplicates;

按理来说这个其实是一个很简单的题目, 不过也是花了很长时间. 这个题目的核心逻辑很简单, 对饮的对于 boundary case 的处理就很麻烦, 每次都有不同的 case 来 break 我的逻辑;

break rather than header condition for termination

以前我一直都是比较不齿用 break 的写法, 尽量想要把所有的 termination condition 的判断都扔在 header 里面, 除非是必须要有多个不同的 exit. 不过这题这种情况, 逻辑本身比较复杂, 这个还是要用 break 比较好, 逻辑的操纵更加自由一些; 这个比直接写 header 要方便的多;
但是这个也不代表 header 就直接扔一个 true 就可以了. 比如这里, 你进入之后就要对 head 进行各种引用(dot), 那么你 header 里面就要加一些保证合法性的判断;

checkpoint

这个也是之前那个 delete node 的时候碰到过的一个思想, 就是在指针操作移动之前, 考虑是否有某一个指针你需要先备份一下, 这样后面的操作会方便很多;

最后的速度是1(18), 中规中矩, 这一题大部分的 submission 都是最优解;


这个是 editorial 的最优解:

public ListNode deleteDuplicates(ListNode head) {  
    ListNode current = head;  
    while (current != null && current.next != null) {  
        if (current.next.val == current.val) {  
            current.next = current.next.next;  
        } else {  
            current = current.next;  
        }  
    }  
    return head;  
}

瞬间看到我自己的错误了, 我强迫自己每一个 iteration 一定要移动head. 人家这里的逻辑就很清晰, 只在必要的时候(也就是两个 val 不相等的时候)才移动 head, 至于相等的时候, 直接就做一个删除就行了;


这是 discussion 上一个 recursion 的最优解:

public ListNode deleteDuplicates(ListNode head) {  
        if (head == null) return head;  
        head.next = deleteDuplicates(head.next);  
        return head.val == head.next.val ? head.next : head;  
}

短小精悍;


Problem Description

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Difficulty:Easy
Category:Algorithms
Acceptance:39.67%
Contributor: LeetCode
Related Topics
linked list

results matching ""

    No results matching ""