[LeetCode Road] Remove Duplicates from Sorted List - Solution/C++

83. Remove Duplicates from Sorted List

Question:

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

Example:

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

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

Source code

Version 1

Idea:
We can use original List to check each elements. If the current pointer of value is equal to the next pointer of value, we use tail->next = tail->next->next to skip the next pointer. So, We can return head that is unduplicated List.

Time complexity: O(n)
Space complexity: O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *tail = head;
        while(tail && tail->next){
            if(tail->val == tail->next->val){
                tail->next = tail->next->next;
            }else{
                tail = tail->next;
            }
        }
        return head;
    }
};

Version 2

Idea:
If we don't want to modify the List of head, we can delcare a new ListNode, as dummy. Before going into the while statement, we must assign a first value of head to tail->next that is a pointer of the list of dummy. Then we can compare a value of tail with a value of head.
Notice: return dummy must be dummy.next, because the first value is an initial value.

The solution is refered to Huahua's Tech Road.

Time complexity: O(n)
Space complexity: O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        tail->next = head;
        while(head){
            while(head && head->val == tail->next->val) head = head->next;
            tail->next->next = head;
            tail = tail->next;
        }
        return dummy.next;
    }
};