Mastering Patterns

[!NOTE] This module explores the core principles of Linked List Patterns, deriving solutions from first principles (Fast/Slow pointers) to build world-class, production-ready expertise.

To truly master Linked Lists, you need to recognize patterns. We’ve covered “Two Pointers” (Fast/Slow). Now let’s apply it to variations.

1. Palindrome Linked List

Problem: Given 1 -> 2 -> 2 -> 1, return true. Given 1 -> 2, return false.

Intuition

We want O(1) Space.

  1. Find the Middle using Fast/Slow pointers.
  2. Reverse the second half of the list.
  3. Compare the first half and the reversed second half node by node.
  4. (Optional) Restore the list (reverse again).

Solutions

Java
Go
public boolean isPalindrome(ListNode head) {
  if (head == null) return true;

  // 1. Find Middle
  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. Reverse Second Half
  ListNode prev = null;
  while (slow != null) {
    ListNode nextTemp = slow.next;
    slow.next = prev;
    prev = slow;
    slow = nextTemp;
  }

  // 3. Compare
  ListNode left = head;
  ListNode right = prev; // Head of reversed half
  while (right != null) {
    if (left.val != right.val) return false;
    left = left.next;
    right = right.next;
  }
  return true;
}

func isPalindrome(head *ListNode) bool {
  if head == nil { return true }

  // 1. Find Middle
  slow, fast := head, head
  for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
  }

  // 2. Reverse
  var prev *ListNode
  for slow != nil {
    nextTemp := slow.Next
    slow.Next = prev
    prev = slow
    slow = nextTemp
  }

  // 3. Compare
  left, right := head, prev
  for right != nil {
    if left.Val != right.Val { return false }
    left = left.Next
    right = right.Next
  }
  return true
}

Complexity

Strategy Time Space Notes
Reverse Half O(N) O(1) Modifies list temporarily.
Array Copy O(N) O(N) Easiest to implement.

2. Intersection of Two Linked Lists

Problem: Find the node where two lists headA and headB intersect.

Intuition: Switch Tracks

Imagine two runners.

  • Runner A runs List A. When they reach the end, they jump to List B head.
  • Runner B runs List B. When they reach the end, they jump to List A head.
  • If they intersect, they will travel Len(A) + Len(B) distance and meet exactly at the intersection point.

Interactive Analysis

Watch the runners switch tracks. They meet because (A + B) == (B + A).

Visual Representation

Runners at start.

Solutions

Java
Go
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  if (headA == null || headB == null) return null;

  ListNode a = headA;
  ListNode b = headB;

  // They will either meet at intersection or at null (end)
  while (a != b) {
    a = (a == null) ? headB : a.next;
    b = (b == null) ? headA : b.next;
  }
  return a;
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
  if headA == nil || headB == nil { return nil }
  a, b := headA, headB

  for a != b {
    if a == nil {
      a = headB
    } else {
      a = a.Next
    }

    if b == nil {
      b = headA
    } else {
      b = b.Next
    }
  }
  return a
}

Complexity

Strategy Time Space Notes
Two Pointers O(N + M) O(1) Switches tracks to equalize length.

3. Remove Nth Node From End

Problem: Remove the n-th node from the end of the list.

Intuition: The Gap Strategy

  1. Move a fast pointer n steps ahead.
  2. Move both slow and fast together until fast hits the end.
  3. slow is now just before the target node. slow.next = slow.next.next.

[!TIP] Use a Dummy Node at the start to handle edge cases (like removing the head itself).

Solutions

Java
Go
public ListNode removeNthFromEnd(ListNode head, int n) {
  ListNode dummy = new ListNode(0);
  dummy.next = head;

  ListNode slow = dummy;
  ListNode fast = dummy;

  // Create gap of n+1
  for (int i = 0; i <= n; i++) {
    fast = fast.next;
  }

  while (fast != null) {
    slow = slow.next;
    fast = fast.next;
  }

  // Remove
  slow.next = slow.next.next;

  return dummy.next;
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
  dummy := &ListNode{Next: head}
  slow, fast := dummy, dummy

  for i := 0; i <= n; i++ {
    fast = fast.Next
  }

  for fast != nil {
    slow = slow.Next
    fast = fast.Next
  }

  slow.Next = slow.Next.Next
  return dummy.Next
}

Complexity

Strategy Time Space Notes
One Pass O(N) O(1) Uses gap of n nodes.

4. Copy List with Random Pointer

Problem: A list where nodes have next and random pointers. Deep copy it.

Intuition: Interweaving

  1. Interweave: Insert copy A' after A. A -> A' -> B -> B'.
  2. Connect Random: curr.next.random = curr.random.next.
  3. Separate: Unzip the lists.

Solutions

Java
Go
// Definition for a Node.
class Node {
  int val;
  Node next;
  Node random;
  public Node(int val) { this.val = val; }
}

public Node copyRandomList(Node head) {
  if (head == null) return null;

  // 1. Interweave
  Node curr = head;
  while (curr != null) {
    Node copy = new Node(curr.val);
    copy.next = curr.next;
    curr.next = copy;
    curr = copy.next;
  }

  // 2. Connect Random
  curr = head;
  while (curr != null) {
    if (curr.random != null) {
      curr.next.random = curr.random.next; // Copy's random points to Random's copy
    }
    curr = curr.next.next;
  }

  // 3. Separate
  Node newHead = head.next;
  curr = head;
  Node copyCurr = newHead;
  while (curr != null) {
    curr.next = curr.next.next; // Restore original
    if (copyCurr.next != null) {
      copyCurr.next = copyCurr.next.next; // Connect copies
    }
    curr = curr.next;
    copyCurr = copyCurr.next;
  }

  return newHead;
}

// Using Hash Map approach for clarity in Go
func copyRandomList(head *Node) *Node {
  if head == nil { return nil }

  m := make(map[*Node]*Node)

  // 1. Copy Nodes
  curr := head
  for curr != nil {
    m[curr] = &Node{Val: curr.Val}
    curr = curr.Next
  }

  // 2. Connect
  curr = head
  for curr != nil {
    m[curr].Next = m[curr.Next]
    m[curr].Random = m[curr.Random]
    curr = curr.Next
  }

  return m[head]
}

Complexity

Strategy Time Space Notes
Interweaving O(N) O(1) Optimal space (excluding output).
Hash Map O(N) O(N) Easier to implement.