LeetCode //C - 203. Remove Linked List Elements

203. Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
 

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

• The number of nodes in the list is in the range $[0,10^4]$.
• 1 <= Node.val <= 50
• 0 <= val <= 50

From: LeetCode
Link: 203. Remove Linked List Elements

Solution:

Ideas:

1. Dummy Node: Create a dummy node that points to the head of the list. This helps handle edge cases, such as when the head of the list itself needs to be removed.

2. Two Pointers: Use two pointers, prev (previous) and curr (current), to traverse the list. prev starts at the dummy node, and curr starts at the head of the list.

3. Traversal: Iterate through the list with the curr pointer:

• If the value of the current node (curr->val) matches the target value to be removed, update the prev->next pointer to skip the current node and point to curr->next, then free the memory of the current node.
• If the value does not match, move both prev and curr pointers forward to the next nodes in the list.

4. Return New Head: After the traversal, the new head of the list will be dummy->next. Return this new head and free the dummy node.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    // Create a dummy node to handle edge cases such as removing the head node
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    
    // Use two pointers, prev and curr, to traverse the list
    struct ListNode *prev = dummy;
    struct ListNode *curr = head;
    
    while (curr != NULL) {
        if (curr->val == val) {
            // Remove curr by linking prev to curr->next
            prev->next = curr->next;
            free(curr);
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    
    // Get the new head
    struct ListNode *newHead = dummy->next;
    free(dummy); // Free the dummy node
    return newHead;
}