Remove Duplicates from Sorted List

update May 5,2018 0:52

LeetCode

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

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

Basic Idea:

两种思路，recursion 和 iteration。

C++ Code

Recursion

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        head->next = deleteDuplicates(head->next);
        return head->val == head->next->val ? head->next : head;
    }
};

Iteration

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* prev = head;
        ListNode* curr = head->next;
        while (curr != nullptr) {
            if (prev->val == curr->val) {
                curr = curr->next;
            } else {
                prev->next = curr;
                prev = curr;
                curr = curr->next;
            }
        }
        prev->next = nullptr;
        return head;
    }
};