# Remove Duplicates from Sorted List II

Medium

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only _distinct _numbers from the original list.

Example 1:

``````Input: 1->2->3->3->4->4->5
Output: 1->2->5``````

Example 2:

``````Input: 1->1->1->2->3
Output: 2->3``````

## Solution

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode dummy = new ListNode(Integer.MIN_VALUE);
ListNode prev = dummy;
}
prev = prev.next;
} else {
}
}
return dummy.next;
}
}``````

### 基本思想：遇到重复节点，就不断删除，非重复节点，就直接前进。

``````public class Solution {

ListNode dummy = new ListNode(0);

// keep deleting the duplicated value
}
} else {
}
}

return dummy.next;
}
}``````

### 用两个指针， 通俗易懂。慢指针永远指着非重复的数， 快指针永远指着最后一个重复的数。

``````class Solution {
}

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;
}

if (slow.next != fast) {
slow.next = fast.next;
} else {
slow = slow.next;
}
fast = fast.next;
}
return dummy.next;
}
}``````

Last updated