Leetcode: Remove Duplicates from Sorted List II 解题报告

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