Linked List Basic Operations

TL;DR

Linked lists enable O(1) insertion/deletion once position known, but require O(n) traversal to find position. Reversal changes pointer directions. Floyd's cycle detection uses fast-slow pointers. Merging combines two lists by rearranging pointers. All operations require careful pointer management to avoid losing references. Understanding prev/next pointer manipulation is crucial for correct implementation.

Core Concepts

Traversal and Manipulation

Linear traversal visits each node sequentially: start at head, follow next pointers until null.

Conditional traversal stops early based on criteria (e.g., find node with value, reach end).

Reverse traversal requires doubly-linked lists or recursive approach since singly-linked lists can only move forward.

Multi-pass traversal iterates multiple times when single pass is insufficient (e.g., find middle then modify from there).

Traversal is O(n) where n is number of nodes.

Node Insertion and Deletion

Insertion at known position is O(1): create new node, update prev.next to new node, new node.next to old next.

Deletion at known position is O(1): update prev.next to skip current node, which becomes garbage collected.

Position-based: Must traverse to find position first, then insert/delete. Total O(n).

Value-based: Search for node by value O(n), then delete O(1).

Key insight: pointer manipulation is O(1), but finding position is O(n).

List Reversal

Iterative approach: Use three pointers (prev, current, next). Traverse list, reverse each node's next pointer. O(n) time, O(1) space.

Recursive approach: Recursively reach end, then backtrack reversing pointers. O(n) time, O(n) space (call stack).

Partial reversal: Reverse only nodes between positions m and n. Attach reversed segment back to rest of list.

In-place reversal: All approaches reverse without creating new list, just rearranging pointers.

Floyd's Cycle Detection

Fast-slow pointers: Slow moves 1 step, fast moves 2 steps. If cycle exists, they meet inside cycle.

Why it works: If no cycle, fast reaches null. If cycle exists, in circular motion, fast will eventually catch slow.

Find cycle start: After detecting cycle, reset slow to head, move both 1 step until they meet. Meeting point is cycle start.

Cycle length: When pointers meet, count steps until they meet again to find cycle length.

List Merging

Merge two sorted lists: Compare heads, attach smaller to result, advance that pointer. O(n+m) time, O(1) space (pointer rearrangement).

Merge K sorted lists: Use min-heap or divide-and-conquer. Each element compared log K times. O(nk log k) time.

In-place merging: Rearrange pointers without extra data structures.

Key Algorithms and Techniques

Iterative Reversal

Three pointers: prev, current, next. Reverse each node's pointer, advance. O(n) time, O(1) space.

Floyd's Cycle Detection

Fast-slow pointers meet if cycle exists. O(n) time, O(1) space.

Merge Two Sorted Lists

Compare heads, attach smaller. Advance smaller's pointer. Continue until one exhausted.

Find Kth Node from End

Two pointers k apart. Advance both together until fast reaches end. Slow points to kth from end.

Remove Nth Node from End

Find (n+1)th from end, remove nth by skipping it.

Practical Example

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Traversal
def print_list(head):
    current = head
    while current:
        print(current.val, end=" -> ")
        current = current.next
    print("None")

# Insertion at head
def insert_at_head(head, val):
    new_node = ListNode(val, head)
    return new_node

# Insertion at specific position
def insert_at_position(head, val, pos):
    if pos == 0:
        return insert_at_head(head, val)
    current = head
    for _ in range(pos - 1):
        if not current or not current.next:
            return head
        current = current.next
    current.next = ListNode(val, current.next)
    return head

# Iterative reversal
def reverse_list_iterative(head):
    prev = None
    current = head
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    return prev

# Recursive reversal
def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    reversed_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return reversed_head

# Floyd's cycle detection
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Find cycle start
def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

# Merge two sorted lists
def merge_sorted_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 if l1 else l2
    return dummy.next

# Delete node at position
def delete_at_position(head, pos):
    if pos == 0:
        return head.next
    current = head
    for _ in range(pos - 1):
        if not current or not current.next:
            return head
        current = current.next
    if current.next:
        current.next = current.next.next
    return head

# Test
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print_list(head)
head = reverse_list_iterative(head)
print_list(head)

Java

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

public class LinkedListOperations {
    // Traversal
    static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // Iterative reversal
    static ListNode reverseIterative(ListNode head) {
        ListNode prev = null, current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }

    // Floyd's cycle detection
    static 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 cycle start
    static ListNode findCycleStart(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    // Merge two sorted lists
    static ListNode mergeSortedLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = l1 != null ? l1 : l2;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        printList(head);
    }
}

TypeScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val: number = 0, next: ListNode | null = null) {
        this.val = val;
        this.next = next;
    }
}

// Traversal
function printList(head: ListNode | null): void {
    let current = head;
    while (current) {
        process.stdout.write(`${current.val} -> `);
        current = current.next;
    }
    console.log("null");
}

// Iterative reversal
function reverseIterative(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let current = head;
    while (current) {
        const nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

// Floyd's cycle detection
function hasCycle(head: ListNode | null): boolean {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

// Find cycle start
function findCycleStart(head: ListNode | null): ListNode | null {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) {
            slow = head;
            while (slow !== fast) {
                slow = slow!.next;
                fast = fast!.next;
            }
            return slow;
        }
    }
    return null;
}

// Merge two sorted lists
function mergeSortedLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0);
    let current = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    current.next = l1 ? l1 : l2;
    return dummy.next;
}

// Test
let head = new ListNode(1, new ListNode(2, new ListNode(3)));
printList(head);
head = reverseIterative(head);
printList(head);

Common Pitfalls

warning

Losing reference to head: When modifying head (insertion at beginning, reversal), must return new head. Caller must use returned value.

Null pointer exceptions: Forgetting to check next != null before accessing next.next causes crashes. Always check before dereferencing.

Infinite loops: Cycle in list causes traversal to loop forever. Always include cycle detection or maximum iteration limit.

Memory leaks: In some languages, deleted nodes not garbage collected if references remain elsewhere. Clear all references.

Incorrect pointer updates: Updating pointers in wrong order loses references. Always save next pointer before changing current.next.

Off-by-one in position tracking: Counting positions from 0 vs 1 causes fencepost errors. Be consistent in indexing.

Self-Check

1. Why does Floyd's cycle detection work? Prove that fast and slow pointers must meet if cycle exists.
2. Explain iterative list reversal step-by-step. What is the role of each pointer?
3. Why does "find kth from end" require two pointers k apart instead of single traversal?

One Takeaway

info

Master pointer manipulation in linked lists: careful state management (prev/current/next), understanding when to return new references (like reversed head), and recognizing cycles with fast-slow pointers. Most linked list problems boil down to correct pointer updates and handling edge cases (empty list, single node, cycles).

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.