Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given
1->2->3->3->4->4->5
, return
1->2->5
.
Given
1->1->1->2->3
, return
2->3
.
SOLUTION 1:
使用一个del标记来删除最后一个重复的字元。
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {
7 * val = x;
8 * next = null;
9 * }
10 * }
11 */
12 public class Solution {
13 public ListNode deleteDuplicates(ListNode head) {
14 if (head == null) {
15 return null;
16 }
17
18 // record the head.
19 ListNode dummy = new ListNode(0);
20 dummy.next = head;
21
22 ListNode cur = dummy;
23
24 // to delete the last node in the list of duplications.
25 boolean del = false;
26
27 while (cur != null) {
28 if (cur.next != null
29 && cur.next.next != null
30 && cur.next.val == cur.next.next.val) {
31 cur.next = cur.next.next;
32 del = true;
33 } else {
34 if (del) {
35 cur.next = cur.next.next;
36 del = false;
37 } else {
38 cur = cur.next;
39 }
40 }
41 }
42
43 return dummy.next;
44 }
45 }
View Code
SOLUTION 2:
使用一个pre, 一个cur来扫描,遇到重复的时候,使用for循环用cur跳过所有重复的元素。
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {
7 * val = x;
8 * next = null;
9 * }
10 * }
11 */
12 public class Solution {
13 public ListNode deleteDuplicates(ListNode head) {
14 if (head == null) {
15 return null;
16 }
17
18 ListNode dummy = new ListNode(0);
19 dummy.next = head;
20
21 ListNode pre = dummy;
22 ListNode cur = pre.next;
23
24 while (cur != null && cur.next != null) {
25 if (cur.val == cur.next.val) {
26 while (cur != null && cur.val == pre.next.val) {
27 cur = cur.next;
28 }
29
30 // delete all the duplication.
31 pre.next = cur;
32 } else {
33 cur = cur.next;
34 pre = pre.next;
35 }
36 }
37
38 return dummy.next;
39 }
40 }
View Code