82 Remove Duplicates from Sorted List II

Search…

82. Remove Duplicates from Sorted List II​
1. Question
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving onlydistinctnumbers from the original list.
For example,
Given1->2->3->3->4->4->5, return1->2->5.
Given1->1->1->2->3, return2->3.
2. Implementation
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode(int x) { val = x; }
7
 * }
8
 */
9
class Solution {
10
    public ListNode deleteDuplicates(ListNode head) {
11
        ListNode dummy = new ListNode(0);
12
        dummy.next = head;
13
​
14
        ListNode preNode = dummy, curNode = head;
15
​
16
        while (curNode != null) {
17
            while (curNode.next != null && curNode.val == curNode.next.val) {
18
                curNode = curNode.next;
19
            } 
20
​
21
            if (preNode.next != curNode) {
22
                preNode.next = curNode.next;
23
            }
24
            else {
25
                preNode = preNode.next;
26
            }
27
            curNode = curNode.next;
28
        }
29
        return dummy.next;
30
    }
31
}
Copied!
3. Time & Space Complexity
时间复杂度O(n), 空间复杂度O(1)

61 Rotate List

83 Remove Duplicates from Sorted List

Last modified 2yr ago

Copy link

Contents

82. Remove Duplicates from Sorted List II

1. Question

2. Implementation

3. Time & Space Complexity

82. Remove Duplicates from Sorted List II​

1. Question

2. Implementation

3. Time & Space Complexity

82. Remove Duplicates from Sorted List II