Common Interview Operations

If you are asked a Linked List question in an interview, there is a 90% chance it involves pointer manipulation. The absolute classic is reversing a list.

1. Reverse a Linked List

Goal: Turn A → B → C → null into C → B → A → null.

The Strategy: Three Pointers

You cannot just flip a pointer blindly, or you will lose the rest of the list. You need three guards:

1. Prev: Tracks the node behind (starts at null).
2. Curr: The node we are processing.
3. Next: Stores curr.next before we break the link.

2. Interactive: Reversal Animator

Watch the pointers dance. Click “Step” to execute one iteration of the loop.

State: Initial. Pointers ready.

while (curr ≠ null) { ... }

Iterative Implementation (O(N) Time, O(1) Space)

Java

public ListNode reverseList(ListNode head) {
  ListNode prev = null;
  ListNode curr = head;

  while (curr != null) {
    ListNode nextTemp = curr.next; // 1. Save next
    curr.next = prev;              // 2. Reverse link
    prev = curr;                   // 3. Move prev
    curr = nextTemp;               // 4. Move curr
  }
  return prev; // New Head
}

Go

func ReverseList(head *ListNode) *ListNode {
  var prev *ListNode
  curr := head

  for curr != nil {
    nextTemp := curr.Next
    curr.Next = prev
    prev = curr
    curr = nextTemp
  }
  return prev
}

---

2. Merge Two Sorted Lists

Goal: Given 1 → 3 → 5 and 2 → 4 → 6, return 1 → 2 → 3 → 4 → 5 → 6.

The “Zipper” Strategy

Imagine a zipper merging two tracks.

1. Create a Dummy Node (Sentinel) to act as the anchor.
2. Compare list1.val and list2.val.
3. Attach the smaller node to your result.
4. Move the pointer forward.
5. Repeat until one list is empty, then attach the remainder.

Implementation

Java

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  ListNode dummy = new ListNode(-1); // Sentinel
  ListNode tail = dummy;

  while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }

  // Attach remainder
  if (list1 != null) tail.next = list1;
  else if (list2 != null) tail.next = list2;

  return dummy.next;
}

Go

func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
  dummy := &ListNode{Val: -1}
  tail := dummy

  for list1 != nil && list2 != nil {
    if list1.Val <= list2.Val {
      tail.Next = list1
      list1 = list1.Next
    } else {
      tail.Next = list2
      list2 = list2.Next
    }
    tail = tail.Next
  }

  if list1 != nil {
    tail.Next = list1
  } else if list2 != nil {
    tail.Next = list2
  }

  return dummy.Next
}

[!TIP] Why the Dummy Node? Without it, you’d have to write extra if/else logic to initialize the head of the result list. The Dummy Node simplifies the code by guaranteeing a non-null start.

In the next chapter, we’ll explore Floyd’s Cycle-Finding Algorithm, one of the most clever algorithms in computer science.