Remove Duplicates from Sorted List

Posted on Edited on In Views:

83.Remove Duplicates from Sorted List

Example 1:

img

1
2
Input: head = [1,1,2]
Output: [1,2]

Example 2:

img

1
2
Input: head = [1,1,2,3,3]
Output: [1,2,3]

个人解答：

双指针

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* deleteDuplicates(ListNode* head) {
    if (!head) {
        return head;
    }
    ListNode* node1 = head;
    ListNode* node2 = head->next;
    while (node2 != nullptr) {
        if (node2->val == node1->val) {
            node1->next = node2->next;
            node2 = node2->next;
        }
        else {
            node1 = node1->next;
            node2 = node2->next;
        }
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }

        return head;
    }
};