Programming
Leetcode-82. Remove Duplicates from Sorted List II
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3]
Output: [2,3]
->重複的數字就刪除
<解題>
- 用slow、fast指標，若fast.next != null && fast.val == fast.next.val，fast指標往後移
- 判斷：slow.next 是否為 fast： -slow.next != fast，代表有重複的數，將他移除（slow.next = fast.next)，記得將指標重置 -else，代表沒有重複的數，兩者指標繼續向後移動
- 迴圈結束，return dummy.next
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode fast = head, slow = dummy;
slow.next = fast;
while(fast != null) {
while (fast.next != null && fast.val == fast.next.val) {
fast = fast.next; //fast指標向後移
}
if (slow.next != fast) { //有重複的數
slow.next = fast.next; //remove the dups
fast = slow.next; //reposition the fast pointer
} else { //no dup, move down both pointer
slow = slow.next;
fast = fast.next;
}
}
return dummy.next;
}
}
Time : O(n) Space : O(1)