Remove sorted list duplicates II

Problem

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

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

Example 2:

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

Accepted on First Attempt 🍺

We try and use a pointer to a pointer. This allows handling special cases like updating head more generically although the approach may be off-putting to some.

Trying it on paper with a picture paid off. There wasn’t even a compilation error 🕺

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  ListNode *skipDups(ListNode *p, int v) {
    while (p && p->val == v) { p = p->next;}
    return p;
  }
public:

  ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode **p = &head;

    while ((*p) && ((*p)->next)) {
      if ((*p)->val == (*p)->next->val) {
        ListNode *n = skipDups(*p, (*p)->val);
        *p = n;
      } else {
        p = &((*p)->next);
      }
    }
    return head;
  }
};

There is a flaw in this solution though. Can you see it?

Where’s my memory? 🕵

That skipDups() function only skips but doesn’t release any memory!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  ListNode *skipDups(ListNode *p, int v) {
    while (p && p->val == v) {
      ListNode *tmp = p;
      p = p->next;
      free(tmp);
    }
    return p;
  }
public:

  ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode **p = &head;

    while ((*p) && ((*p)->next)) {
      if ((*p)->val == (*p)->next->val) {
        ListNode *n = skipDups(*p, (*p)->val);
        *p = n;
      } else {
        p = &((*p)->next);
      }
    }
    return head;
  }
};