Linked List Basics and Core Operations

Linked List Memory Model

Linked lists and arrays are fundamentally different data structures, with the primary difference rooted in their memory layout:

Array (Contiguous):
Memory Address: 1000  1004  1008  1012
Data:          [ A  |  B  |  C  |  D ]

Linked List (Scattered):
[ A | 3100 ] → [ B | 0800 ] → [ C | 2400 ] → [ D | null ]
  Addr: 1000      Addr: 3100      Addr: 0800      Addr: 2400

Each node in a linked list consists of two parts: Data and a Pointer (or Reference) to the next node. Nodes can be scattered anywhere in memory, linked together by these pointers to form a logically continuous sequence.

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

Comparison with Arrays

Dummy Node Technique

The Dummy Node (or Sentinel Node) is a crucial technique in linked list operations. It eliminates special cases for the head of the list.

The Problem: When inserting or deleting nodes, the head node lacks a predecessor, often requiring separate logic (special "if-head" checks).

The Solution: Prepend a "dummy" node (with an arbitrary value, usually 0) before the actual head. It becomes the predecessor of all real nodes.

// Example: Remove all elements from a linked list that have a specific value
ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;
    
    while (cur.next != null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;  // Skip the target node
        } else {
            cur = cur.next;
        }
    }
    return dummy.next;  // The actual new head (original head might have been deleted)
}

Without a dummy node, you would need complex logic to handle cases where the head itself needs to be removed:

// Tedious approach without a dummy node
while (head != null && head.val == val) {
    head = head.next; // Special handling for head
}
ListNode cur = head;
// ... continue processing the rest

Rule of Thumb: For almost any problem involving inserting or deleting nodes, create a dummy node first.

Two Pointers Technique

Fast & Slow Pointers: Finding the Middle

// Floyd's Algorithm: Move fast pointer by 2 steps and slow pointer by 1 step.
// When 'fast' reaches the end, 'slow' will be exactly at the middle.
ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // For even lengths, slow points to the start of the second half
}

Visual Step-through: List: 1 → 2 → 3 → 4 → 5

1. Initial: slow=1, fast=1
2. Step 1: slow=2, fast=3
3. Step 2: slow=3, fast=5
4. Stop: fast.next is null. slow=3 is the middle. ✓

Fast & Slow Pointers: Cycle Detection

// If a cycle exists, the fast pointer will eventually "lap" and meet the slow pointer.
boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;  // Detected a cycle
    }
    return false;  // No cycle found
}

Intuition: Imagine two runners on a track. If the track is a circle, the faster runner will eventually catch up to the slower runner from behind. If the track is a straight line, the faster runner just reaches the finish line first.

Fast & Slow Pointers: Finding the Cycle Entrance

// 1. Detect cycle using the logic above.
// 2. The key mathematical insight: distance from head to entrance = distance from meeting point to entrance.
ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // Found intersection point
            fast = head; // Reset fast to head
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next; // Both move at same speed
            }
            return slow;  // Entrance discovered
        }
    }
    return null;
}

Two Pointers: Finding the K-th Node from the End

// Move 'fast' pointer k steps ahead first, then move both at the same speed.
ListNode findKthFromEnd(ListNode head, int k) {
    ListNode slow = head, fast = head;
    for (int i = 0; i < k; i++) {
        if (fast == null) return null; // Handle k > length
        fast = fast.next;
    }
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

Reversing a Linked List

Master both iterative and recursive implementations.

Iterative Reverse (Entire List)

ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode nextTemp = cur.next;  // Save successor
        cur.next = prev;               // Flip the pointer
        prev = cur;                    // Advance prev
        cur = nextTemp;                // Advance cur
    }
    return prev;  // Prev will be the new head
}

Visual Trace: Initial: null ← [1] → [2] → [3] → null

1. prev=1, cur=2: null ← [1] [2] → [3]
2. prev=2, cur=3: null ← [1] ← [2] [3]
3. prev=3, cur=null: [1] ← [2] ← [3] Returns 3.

Reversing a Range (Partial Reverse from left to right)

ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;

    // Move 'pre' to node just before the range
    for (int i = 1; i < left; i++) pre = pre.next;

    ListNode cur = pre.next; // Start of the reverse range
    for (int i = 0; i < right - left; i++) {
        // "Insertion" method: pull next node to the front of the range
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy.next;
}

Merging Lists

Merge Two Sorted Lists

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = (l1 != null) ? l1 : l2;  // Append the remaining part
    return dummy.next;
}

Common Pitfalls and Best Practices

1. Saving the next Pointer: Always save cur.next before modifying it during a reversal or deletion, otherwise you lose access to the rest of the list.
2. Memory Management: In Java, unreferenced nodes are automatically garbage collected. However, in low-level languages like C++, you must explicitly delete nodes to avoid memory leaks.
3. Null Check Everything: Before accessing node.next.val, ensure that both node and node.next are not null.

// Safest loop condition
while (cur != null && cur.next != null) {
    // Operations...
}

Summary

The core advantage of linked lists is dynamic memory allocation and O(1) insertion/deletion (given the predecessor), at the cost of O(n) random access.

Three must-know techniques: