Linked List

Back to DSA & Algorithms/00 - Roadmap Overview

What is a Linked List?

A linked list is a chain of nodes, where each node contains a value and a pointer to the next node. Unlike arrays, the nodes are NOT stored contiguously in memory — they're scattered around, connected by pointers.

Array:   [10][20][30][40]     ← contiguous, adjacent slots

Linked:  [10]→[20]→[30]→[40]→null
         Each box is somewhere in memory, connected by arrows (pointers)

Singly vs Doubly Linked List

Singly:  [val|next] → [val|next] → [val|next] → null
         Can only go FORWARD

Doubly:  null ← [prev|val|next] ⇄ [prev|val|next] ⇄ [prev|val|next] → null
         Can go FORWARD and BACKWARD

Why Use Linked Lists?

OperationArrayLinked ListWinner
Access by indexO(1)O(n)Array
SearchO(n)O(n)Tie
Insert at headO(n)O(1)LL
Insert at tailO(1)*O(1)**Tie
Insert in middleO(n)O(1)***LL
DeleteO(n)O(1)***LL
MemoryCompactExtra pointer overheadArray

*amortized, **if you have tail pointer, ***if you have the node reference

In practice: Arrays are almost always faster due to cache locality. Linked lists shine when you need frequent insertions/deletions at known positions (like LRU cache).

Java Node Definition

java
class ListNode {
    int val;
    ListNode next;

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

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

// Create: 1 → 2 → 3
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3)));

// Traverse
ListNode curr = head;
while (curr != null) {
    System.out.println(curr.val);
    curr = curr.next;
}

The Golden Rule: DRAW IT OUT

Linked list problems are visual. The #1 mistake is trying to solve them in your head. Draw boxes and arrows on paper. Trace through your pointer operations step by step.

Before: A → B → C → D
Operation: Remove B
After:  A → C → D

Step 1: A.next = A.next.next  (A.next was B, B.next was C, so now A.next = C)
Step 2: B is now disconnected (garbage collected)

Pattern 1: Dummy Head Node

What it is

Create a fake node before the real head. This eliminates edge cases where the head itself might change (deletion of head, insertion before head).

When to use it

  • Removing nodes (what if you remove the head?)
  • Merging lists (which list provides the new head?)
  • Any operation where the head might change

The Mental Model

It's like having a "Title Page" before your book's first chapter. Even if you rip out Chapter 1, the Title Page is still there, and titlePage.next points to whatever the new Chapter 1 is.

Step-by-Step: Remove Nth Node From End

java
// Remove the Nth node from the END of the list.
// Input: 1→2→3→4→5, n=2
// Output: 1→2→3→5 (removed the 4)

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);    // Dummy before head

    // Use two pointers, n+1 apart
    ListNode slow = dummy;
    ListNode fast = dummy;

    // Move fast n+1 steps ahead
    for (int i = 0; i < n + 1; i++) {
        fast = fast.next;
    }

    // Move both until fast reaches the end
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }

    // Now slow is RIGHT BEFORE the node to remove
    slow.next = slow.next.next;

    return dummy.next;   // Not head! (head might have been removed)
}

// Why n+1? Because we want slow to be ONE BEFORE the target.
//
// Walkthrough: 1→2→3→4→5, n=2
// dummy→1→2→3→4→5→null
// After moving fast 3 steps: fast=3, slow=dummy
// Move both:
//   fast=4, slow=1
//   fast=5, slow=2
//   fast=null, slow=3
// slow.next = slow.next.next → 3.next = 5 (skipping 4)
// Result: 1→2→3→5

Problems

Pattern 2: Fast & Slow Pointers (Floyd's Tortoise and Hare)

What it is

Two pointers traverse the list at different speeds. Slow moves 1 step at a time, fast moves 2 steps. This detects cycles, finds the middle, and more.

Why It Works: Cycle Detection

Imagine two runners on a circular track. The fast runner laps the slow runner eventually — they MUST meet. On a straight track (no cycle), the fast runner just reaches the end.

No cycle:  fast reaches null → no cycle
           slow: 1→2→3
           fast: 1→3→5→null

Cycle:     fast catches up to slow → cycle exists
           1 → 2 → 3 → 4
                    ↑       ↓
                    6 ← 5
           Eventually slow and fast will be on the same node

Step-by-Step: Find Middle

java
public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;           // 1 step
        fast = fast.next.next;      // 2 steps
    }

    return slow;  // When fast reaches end, slow is at middle
}

// Why? Fast moves 2x speed. When fast finishes the list (2n steps),
// slow has done n steps = exactly the middle.
//
// 1 → 2 → 3 → 4 → 5
// s=1,f=1 → s=2,f=3 → s=3,f=5 → fast.next=null, stop
// slow = 3 = middle ✓
//
// 1 → 2 → 3 → 4 → 5 → 6
// s=1,f=1 → s=2,f=3 → s=3,f=5 → s=4,f=null(past 6)
// slow = 4 = right-middle ✓

Finding Cycle Start (Floyd's Complete Algorithm)

java
public ListNode detectCycle(ListNode head) {
    // Phase 1: Detect if cycle exists
    ListNode slow = head;
    ListNode fast = head;
    boolean hasCycle = false;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) {
        return null;  // No cycle
    }

    // Phase 2: Find where cycle begins
    // Mathematical proof: distance from head to cycle start
    //                   = distance from meeting point to cycle start
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;    // Both move at speed 1 now!
    }

    return slow;  // This is the cycle start
}

// Why does Phase 2 work?
// Let's say:
//   L = distance from head to cycle start
//   C = cycle length
//   When they meet, slow has traveled L + x, fast has traveled L + x + nC
//   Since fast = 2 * slow: L + x + nC = 2(L + x)
//   Simplify: nC = L + x → L = nC - x
//   So walking L steps from the meeting point = walking to cycle start!

Problems

Pattern 3: Reverse Linked List

What it is

Reverse the direction of all pointers. The last node becomes the head.

This is THE most important linked list operation. It appears as a sub-problem in many harder questions.

The Mental Model

Three people in a conga line: each person has their hands on the shoulders of the person in front. To reverse: each person turns around and puts their hands on the person who was BEHIND them.

Before: null ← 1 → 2 → 3 → null
After:  null ← 1 ← 2 ← 3
               ↑             ↑
               tail          new head

Step-by-Step

java
public ListNode reverseList(ListNode head) {
    ListNode prev = null;     // Will become the new tail (null = end)
    ListNode curr = head;     // Start at the original head

    while (curr != null) {
        ListNode nextNode = curr.next;   // Save the next node (we're about to lose it!)
        curr.next = prev;                // Reverse the pointer
        prev = curr;                     // Move prev forward
        curr = nextNode;                 // Move curr forward
    }

    return prev;  // prev is now the new head
}

// Walkthrough: 1 → 2 → 3
//
// Step 0: prev=null, curr=1
//   nextNode = 2
//   1.next = null (was 2, now points backward)
//   prev = 1, curr = 2
//   State: null ← 1    2 → 3
//
// Step 1: prev=1, curr=2
//   nextNode = 3
//   2.next = 1 (points backward)
//   prev = 2, curr = 3
//   State: null ← 1 ← 2    3
//
// Step 2: prev=2, curr=3
//   nextNode = null
//   3.next = 2 (points backward)
//   prev = 3, curr = null
//   State: null ← 1 ← 2 ← 3
//
// Return prev = 3 (new head)

Reverse a Sub-section

java
// Reverse nodes from position left to right (1-indexed)
// Input: 1→2→3→4→5, left=2, right=4
// Output: 1→4→3→2→5

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;

    // Navigate to the node just before 'left'
    for (int i = 0; i < left - 1; i++) {
        prev = prev.next;
    }
    // prev = node 1 (before the reversed section)

    ListNode curr = prev.next;  // curr = node 2 (start of reversed section)

    // Reverse by pulling nodes one at a time to after prev
    for (int i = 0; i < right - left; i++) {
        ListNode nodeToMove = curr.next;
        curr.next = nodeToMove.next;
        nodeToMove.next = prev.next;
        prev.next = nodeToMove;
    }

    return dummy.next;
}

// Visualized:
// Start:     dummy→1→[2→3→4]→5   (brackets = section to reverse)
// Iteration 1: Pull 3 before 2 → dummy→1→[3→2→4]→5
// Iteration 2: Pull 4 before 3 → dummy→1→[4→3→2]→5
// Done!

Palindrome Linked List (Combines Middle + Reverse)

java
public boolean isPalindrome(ListNode head) {
    // Step 1: Find middle
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Step 2: Reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode nextNode = slow.next;
        slow.next = prev;
        prev = slow;
        slow = nextNode;
    }

    // Step 3: Compare first half with reversed second half
    ListNode left = head;
    ListNode right = prev;
    while (right != null) {
        if (left.val != right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }

    return true;
}

Problems

Pattern 4: Merge Sorted Lists

Step-by-Step

java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    curr.next = (l1 != null) ? l1 : l2;   // Attach remaining nodes
    return dummy.next;
}

// Merge K sorted lists: use a min-heap (PriorityQueue)
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

    for (ListNode l : lists) {
        if (l != null) {
            heap.offer(l);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        curr.next = node;
        curr = curr.next;
        if (node.next != null) {
            heap.offer(node.next);
        }
    }

    return dummy.next;
}

Problems

Pattern 5: LRU Cache (Design)

What it is

Least Recently Used cache: A fixed-size cache that evicts the least recently accessed item when full. Combines a hash map (O(1) lookup) with a doubly linked list (O(1) insertion/removal).

Why Doubly Linked List?

The list maintains access order. Most recently used at the front, least recently used at the back. When you access an item, move it to the front. When you evict, remove from the back. Both operations need O(1) → doubly linked list.

java
class Node {
    int key;
    int val;
    Node prev;
    Node next;

    Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    private int capacity;
    private HashMap<Integer, Node> cache;

    // Dummy head and tail (simplify edge cases)
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();

        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    /** Remove a node from the doubly linked list. */
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /** Add a node right after head (most recently used). */
    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        remove(node);         // Remove from current position
        addToFront(node);     // Move to front (most recent)
        return node.val;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            remove(cache.get(key));
        }

        Node node = new Node(key, value);
        cache.put(key, node);
        addToFront(node);

        if (cache.size() > capacity) {
            // Evict least recently used (node before tail)
            Node lru = tail.prev;
            remove(lru);
            cache.remove(lru.key);
        }
    }
}

Problems

Things You MUST Be Aware Of

1. Pointer Order Matters

java
// WRONG: Loses the reference to next node
curr.next = prev;        // Now how do we get to the original next?

// RIGHT: Save next before modifying
ListNode nextNode = curr.next;   // Save it!
curr.next = prev;                // Now safe to modify

2. Always Use Dummy Node When Head Might Change

java
// If you might remove the head, return dummy.next, NOT head
ListNode dummy = new ListNode(0, head);
// ... operations ...
return dummy.next;  // The real head after all operations

3. While Conditions for Fast/Slow

java
while (fast != null && fast.next != null) {    // For finding middle, cycle detection
// Need BOTH checks:
//   fast != null → avoids crash on odd-length lists
//   fast.next != null → avoids crash when fast is at the last node
}

4. Don't Lose Nodes

java
// When reconnecting nodes, always save references BEFORE modifying
// Draw it out. Trace every pointer change. It's worth the 30 seconds.

Decision Guide

Head might change (insert/delete at head)?
  └── Use dummy node

Find middle / detect cycle?
  └── Fast & slow pointers

Reverse (full or partial)?
  └── prev/curr/next three-pointer technique

Merge sorted lists?
  └── Dummy node + compare heads

"Design a cache with O(1) get/put"?
  └── HashMap + Doubly Linked List

Remove Nth from end?
  └── Two pointers, N+1 apart + dummy node