Linked List

Linked List Fundamentals

A linked list is a linear data structure where elements are stored in nodes. Each node contains data and a reference (pointer) to the next node.

Visual Example

[1] → [2] → [3] → [4] → null

Node Structure

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

Linked List vs Array

Common Operations

// Create a linked list: 1 → 2 → 3
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

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

// Insert at beginning
ListNode newNode = new ListNode(0);
newNode.next = head;
head = newNode;

// Delete a node (given reference)
prev.next = prev.next.next;

When to Use Linked List

1. Frequent insertions/deletions at beginning
2. Unknown size - dynamic size
3. No random access needed
4. Implementing stacks, queues, graphs
5. LRU Cache implementation

Linked List Problems

1. Reverse Linked List (LeetCode 206)

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
// Time: O(n), Space: O(1)

2. Detect Cycle (LeetCode 141)

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}
// Time: O(n), Space: O(1)

3. Merge Two Sorted Lists (LeetCode 21)

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    current.next = (list1 != null) ? list1 : list2;
    return dummy.next;
}

4. Middle of Linked List (LeetCode 876)

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Fast/Slow Pointer Pattern

Use two pointers moving at different speeds:

• Cycle detection: If they meet, there's a cycle
• Find middle: Fast reaches end, slow is at middle
• Nth from end: Move fast n steps first, then both move