Linked List Fundamental Concepts (Sentinel Node, Basic Operations)

Why Use a Linked List?

Linked lists are ideal for scenarios requiring frequent insertions and deletions where random access is not a priority.

Sentinel Nodes (Dummy Nodes)

The Sentinel node is a universal technique for handling linked list edge cases gracefully.

By adding a dummy node before the head, you eliminate the need for special handling of the actual head node during modifications:

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;

// Perform operations on cur.next instead of cur directly
// Finally, return dummy.next (the new head)

Common Scenarios: Deleting the head, merging lists, or any operation that might alter the start of the list.

Basic Operation Templates

Insertion at Target Position

// Insert newNode after node 'prev'
void insertAfter(ListNode prev, ListNode newNode) {
    if (prev == null) return;
    newNode.next = prev.next;
    prev.next = newNode;
}

Deleting a Node

// Delete the node following 'prev'
void deleteAfter(ListNode prev) {
    if (prev != null && prev.next != null) {
        prev.next = prev.next.next;
    }
}

// Delete the current node (requires next to exist)
// Trick: Copy the next node's value and bridge over it
void deleteSelf(ListNode node) {
    if (node == null || node.next == null) return;
    node.val = node.next.val;
    node.next = node.next.next;
}

Linked List Traversal Techniques

Finding the Middle (Fast & Slow Pointers)

// For even lengths, slow stops at the end of the first half
ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Retrieving Length

int getLength(ListNode head) {
    int len = 0;
    while (head != null) { 
        len++; 
        head = head.next; 
    }
    return len;
}

Common Mistakes

1. NullPointerException: Always verify node != null && node.next != null before accessing properties.
2. Losing Successors: Save next = cur.next before modifying cur.next.
3. Returning the Wrong Head: When using a sentinel node, remember to return dummy.next, not the sentinel itself.

Debugging Tips

Printing the list structure can greatly help in tracking pointer redirection:

static String listToString(ListNode head) {
    StringBuilder sb = new StringBuilder("[");
    ListNode cur = head;
    while (cur != null) {
        sb.append(cur.val);
        if (cur.next != null) sb.append(" -> ");
        cur = cur.next;
    }
    return sb.append("]").toString();
}