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