Linked Lists

A linked list stores elements in nodes where each node points to the next. Singly linked: each node has next. Doubly linked: each node has next and prev. Key techniques: fast/slow pointers (cycle detection, middle element), dummy head (simplifies edge cases), reversal (iterative and recursive). O(1) insert/delete at head, O(n) access/search.

Key Concepts

Deep Dive: Node Definition

// Singly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// Doubly linked list
class DListNode {
    int val;
    DListNode next, prev;
    DListNode(int val) { this.val = val; }
}

Deep Dive: Reverse a Linked List

Iterative (O(n) time, O(1) space):

public ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Recursive:

public ListNode reverseRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Deep Dive: Fast/Slow Pointer (Floyd's)

Detect cycle:

public 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;
    }
    return false;
}

Find middle node:

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

Deep Dive: Merge Two Sorted Lists

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;
    return dummy.next;
}

Common Interview Questions

• Reverse a linked list
• Detect cycle in a linked list
• Find the middle of a linked list
• Merge two sorted linked lists
• Remove N-th node from end
• Check if linked list is palindrome
• Intersection of two linked lists
• LRU Cache (uses doubly linked list + HashMap)