203. Remove Linked List Elements

This problem requires removing all nodes from a singly linked list that have a specific value. Two common approaches demonstrate key linked list operation patterns: using the original head node directly, and using a dummy head node to unify handling of all nodes.

Aproach 1: Without Dummy Head

When operating without a dummy head, we first handle edge cases where the head node itself needs to be removed. After ensuring the head is valid, we traverse the list starting from the head, checking each subsequent node for the target value.

/**
 * 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* removeElements(ListNode* head, int target) {
        // Remove all leading nodes with the target value
        while (head != nullptr && head->val == target) {
            ListNode* tempNode = head;
            head = head->next;
            delete tempNode;
        }
        
        // If list is empty after removing leading nodes, return immediately
        if (head == nullptr) {
            return head;
        }
        
        // Traverse the list to remove non-head nodes with target value
        ListNode* current = head;
        while (current->next != nullptr) {
            if (current->next->val == target) {
                ListNode* tempNode = current->next;
                current->next = current->next->next;
                delete tempNode;
            } else {
                current = current->next;
            }
        }
        
        return head;
    }
};

Approach 2: With Dummy Head

Using a dummy head node eliminates the need for separate logic to handle the head node, as all nodes can be treated uniformly. The dummy head acts as a placeholder before the actual head, simplifying the traversal and removal process.

/**
 * 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* removeElements(ListNode* head, int target) {
        // Create a dummy head pointing to the original head
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* current = dummyHead;
        
        // Traverse the list to remove nodes with target value
        while (current->next != nullptr) {
            if (current->next->val == target) {
                ListNode* tempNode = current->next;
                current->next = current->next->next;
                delete tempNode;
            } else {
                current = current->next;
            }
        }
        
        // Update head to the new valid head and clean up dummy node
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

707. Design Linked List

This problem requires implementing a custom singly linked list with core operations: accessing elements, adding nodes at the head, tail, or specific index, and deleting nodes at a given index. Using a dummy head simplifies all operations and avoids edge-case handling for the head node.

class MyLinkedList {
private:
    struct Node {
        int value;
        Node* next;
        Node(int val) : value(val), next(nullptr) {}
    };
    
    Node* dummyHead;
    int size;

public:
    MyLinkedList() {
        dummyHead = new Node(0);
        size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        Node* current = dummyHead->next;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }
        return current->value;
    }
    
    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        Node* current = dummyHead;
        while (current->next != nullptr) {
            current = current->next;
        }
        Node* newNode = new Node(val);
        current->next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        Node* current = dummyHead;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }
        Node* newNode = new Node(val);
        newNode->next = current->next;
        current->next = newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        Node* current = dummyHead;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }
        Node* tempNode = current->next;
        current->next = tempNode->next;
        delete tempNode;
        tempNode = nullptr; // Avoid dangling pointer
        size--;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206. Reverse Linked List

Reversing a singly linked list can be efficiently done using an iterative approach with three pointers to track the current node, its previous node, and the next node (to avoid losing the rest of the list during reversal).

/**
 * 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* reverseList(ListNode* head) {
        ListNode* current = head;
        ListNode* previous = nullptr;
        ListNode* nextNode = nullptr;
        
        while (current != nullptr) {
            // Store next node to maintain list traversal
            nextNode = current->next;
            // Reverse the current node's pointer
            current->next = previous;
            // Move previous and current pointers forward
            previous = current;
            current = nextNode;
        }
        
        return previous;
    }
};