LeetCode 82. Remove Duplicates from Sorted List II

contributed by < Eric Lin >

Aim

• Provide solutions for the LeetCode 82. Remove Duplicates from Sorted List II

Recursive method

• line 13: If the next node exists and its value is not a duplicate, proceed to line 20.
• line 15: When a duplicate value is found, skip the current node and advance to the next node in the list.
• line 17: After skip all consecutive nodes with the same value, continue traversing the remaining nodes of the linked list.
• line 20: Establish links for the subsequent nodes in the processed list.

Notice that A && (B == C) is equal to A && B == C because == has a higher precedence than && according to C Operator Precedence.

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (head->next && head->val == head->next->val) {
        /* Remove all duplicate numbers */
        while (head->next && head->val == head->next->val)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

source: 2022q1 week 1 quiz

Iterative method

• line 13: Initial a double pointer **currto the address of the head. This allows manipulation of the original list while traversing it.
• line 18: If duplicates are found, skip all consecutive nodes with the same value.
• line 20: Adjust the *curr to point to the next node with distinct value.
• line 22: If no duplicates are found, move the **curr to the next node, continuing the traversal.

Using a double pointer allows you to modify the pointer that points to the current node without affecting the original head pointer.

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    struct ListNode **curr = &head;

    while (*curr && (*curr)->next) {
        if ((*curr)->val == (*curr)->next->val) {
            /* Remove all duplicate numbers */
            while ((*curr)->next && (*curr)->val == (*curr)->next->val)
                *curr = (*curr)->next;
            *curr = (*curr)->next;
        } else {
            curr = &(*curr)->next;
        }
    }
    return head;
}

TODO: Circular doubly-link list