LeetCode 203: Removing Linked List Elements

When deleting nodes from a singly linked list, handling the head node requires a specific strategy. Unlike internal nodes, which are removed by updating the next reference of their predecessor, the head node has no preceding node. To remove the head, we must simply advance the head reference to the next node in the sequence. The following solution first skips any leading nodes that match the target value, then iterates through the remainder of the list to remove internal matches.

class Solution {
    public ListNode removeElements(ListNode root, int target) {
        // Remove all leading nodes that match the target
        while (root != null && root.val == target) {
            root = root.next;
        }
        
        ListNode current = root;
        // Iterate through the rest of the list
        while (current != null) {
            // If the next node matches, bypass it
            while (current.next != null && current.next.val == target) {
                current.next = current.next.next;
            }
            current = current.next;
        }
        return root;
    }
}

LeetCode 707: Designing a Custom Linked List

Implementing a linked list from scratch is greatly simplified by using a dummy head node (sentinel). This dummy node, typically initialized with a value of 0, sits before the actual data elements. It allows operations at the head of the list (index 0) to follow the exact same logic as operations anywhere else in the list. Each method must handle boundary conditions, such as an invalid index, before performing the logic. Both insertion at the head and tail can be treated as specific cases of insertion at a given index.

class MyLinkedList {
    private int length;
    private ListNode dummyHead;

    public MyLinkedList() {
        this.length = 0;
        this.dummyHead = new ListNode(0);
    }

    public int get(int index) {
        if (index < 0 || index >= length) {
            return -1;
        }
        ListNode pointer = dummyHead;
        // Traverse to the node immediately before the target index
        for (int i = 0; i <= index; i++) {
            pointer = pointer.next;
        }
        return pointer.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(length, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > length) {
            return;
        }
        index = Math.max(0, index);
        length++;
        
        ListNode predecessor = dummyHead;
        // Move to the node preceding the insertion point
        for (int i = 0; i < index; i++) {
            predecessor = predecessor.next;
        }
        
        ListNode newNode = new ListNode(val);
        newNode.next = predecessor.next;
        predecessor.next = newNode;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= length) {
            return;
        }
        length--;
        
        ListNode predecessor = dummyHead;
        for (int i = 0; i < index; i++) {
            predecessor = predecessor.next;
        }
        // Bypass the node to be deleted
        predecessor.next = predecessor.next.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    
    public ListNode(int val) {
        this.val = val;
    }
}

LeetCode 206: Reversing a Linked List

Reversing a linked list involves manipulating pointers so that each node points to its prdeecessor instead of its successor. This is distinct from reversing an array due to the non-contiguous memory structure.

Iterative Approach:

The iterative method uses two or three pointers to traverse the list while reversing links. We maintain a reference to the previous node, the current node, and temporarily store the next node before breaking the link.

class Solution {
    public ListNode reverseList(ListNode startNode) {
        ListNode previous = null;
        ListNode current = startNode;
        
        while (current != null) {
            ListNode nextNode = current.next; // Store next node
            current.next = previous;          // Reverse link
            previous = current;               // Move previous forward
            current = nextNode;               // Move current forward
        }
        return previous; // New head of the reversed list
    }
}

Recursive Approach:

Recursion allows us to traverse to the end of the list first, then reverse the links as the call stack unwinds. The base case identifies the last node (or an empty list), which becomes the new head. As we return, we reverse the link between the current node and its successor.

class Solution {
    public ListNode reverseList(ListNode node) {
        // Base case: if empty or single node, return it
        if (node == null || node.next == null) {
            return node;
        }
        
        // Recursively reverse the rest of the list
        ListNode newHead = reverseList(node.next);
        
        // Reverse the link for the current node
        node.next.next = node;
        node.next = null;
        
        return newHead;
    }
}