Common Interview Operations

[!NOTE] This module explores the core principles of Operations (Reverse, Merge), deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

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.

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 Analysis

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

State: Initial. Pointers ready.

while (curr ≠ null) { ... }

---

3. Implementation

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

Java

Go

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
}

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
}

---

4. 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.

Java

Go

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;
}

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
}

Complexity Analysis

Operation	Time	Space	Notes
Reverse	O(N)	O(1)	Linear scan, constant pointer manipulation.
Merge	O(N + M)	O(1)	Linear scan of both lists.