Coding Exercise – Remove Duplicates From Sorted List – C++ – Online Judge

Question

:

Given a sorted list represented by a directional link structure (as follows), remove the duplicates and return the new list.

1
2
3
4
5
6
7
8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

Original Problem Page: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/

Examples:

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

The given list is sorted, meaning that we can just check the adjacent (neighbour) nodes to see if there is duplicate. Remove duplicates until there isn’t and move forward (to its next) the current pointer. When comparing neighbours, always compare the current node and its next pointer. The first pointer (*head) should always be preserved as we should keep the first element (it is a reference node). If there is a duplicate, delete it and re-point the next pointer to its next pointer (that effectively skips the duplicate)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *p = head; // head should not change
        while ((p != NULL) && (p->next != NULL)) { // at least two elements
            ListNode *n = p->next; // check next value
            if (n->val == p->val) {  // duplicate
                p->next = n->next; // skip a node
                delete n;  // delete duplicate
            } else p = p->next; // move forward
        }
        return head;
    }
};

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *p = head; // head should not change
        while ((p != NULL) && (p->next != NULL)) { // at least two elements
            ListNode *n = p->next; // check next value
            if (n->val == p->val) {  // duplicate
                p->next = n->next; // skip a node
                delete n;  // delete duplicate
            } else p = p->next; // move forward
        }
        return head;
    }
};

The overall complexity is O(n), and there is no additional space required, everything is done in place.

–EOF (The Ultimate Computing & Technology Blog) —