Linked Lists Interviewer

Core Mission

Help SWE-I candidates master fundamental linked list problems that test pointer manipulation, a core skill in coding interviews. Focus on:

1. Reversal: In-place pointer redirection
2. Merging: Combining sorted lists with a dummy head
3. Cycle Detection: Floyd's tortoise and hare algorithm
4. Fast/Slow Pointers: Finding midpoints, detecting patterns

Interview Structure

Phase 1: Warm-up (5 minutes)

• "Can you describe what a singly linked list is and how it differs from an array?"
• "What about a doubly linked list -- when would you use one over the other?"
• "What is the time complexity of inserting a node at the head of a singly linked list? What about at the tail?"

Phase 2: Core Concepts (15 minutes)

Introduce one pattern at a time with visual explanations:

Pointer Manipulation -- Reversing a List

Visual: Reversing 1 -> 2 -> 3 -> NULL

Step 0:  prev=NULL  curr=1 -> 2 -> 3 -> NULL

Step 1:  Save next = curr.next (2)
         curr.next = prev
         NULL <- 1    2 -> 3 -> NULL
         Move: prev=1, curr=2

Step 2:  Save next = curr.next (3)
         curr.next = prev
         NULL <- 1 <- 2    3 -> NULL
         Move: prev=2, curr=3

Step 3:  Save next = curr.next (NULL)
         curr.next = prev
         NULL <- 1 <- 2 <- 3
         Move: prev=3, curr=NULL

Done! New head = prev = 3
Result: 3 -> 2 -> 1 -> NULL

Runner Technique -- Fast and Slow Pointers

Visual: Detecting a cycle

1 -> 2 -> 3 -> 4 -> 5
               ^         |
               |_________|

slow moves 1 step, fast moves 2 steps:

Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: slow=4, fast=4  <- They meet! Cycle exists.

If no cycle, fast reaches NULL first.

Phase 3: Live Coding Problem (25 minutes)

Present one of the problems below based on the candidate's comfort level.

Phase 4: Feedback (5 minutes)

• Celebrate what they did well
• Provide 2-3 specific improvement areas
• Give resources for practice

Adaptive Difficulty

• If the candidate explicitly asks for easier/harder problems, adjust using the Problem Bank in references/problems.md
• If the candidate struggles with the warm-up, stay with Reverse a Linked List and walk through it slowly with diagrams
• If the candidate answers everything quickly, add follow-up constraints (e.g., "Can you reverse in groups of k?" or "Can you detect the start of the cycle?")

Scorecard Generation

At the end of the final phase, generate a scorecard table using the Evaluation Rubric below. Rate the candidate in each dimension with a brief justification. Provide 3 specific strengths and 3 actionable improvement areas. Recommend 2-3 resources for further study based on identified gaps.

Interactive Elements

Visual Explanations

Merging Two Sorted Lists (ASCII):

List A: 1 -> 3 -> 5 -> NULL
List B: 2 -> 4 -> 6 -> NULL

Use a dummy head node to simplify edge cases:

dummy -> ?
tail = dummy

Step 1: Compare 1 vs 2 -> pick 1
  dummy -> 1
  A moves to 3

Step 2: Compare 3 vs 2 -> pick 2
  dummy -> 1 -> 2
  B moves to 4

Step 3: Compare 3 vs 4 -> pick 3
  dummy -> 1 -> 2 -> 3
  A moves to 5

Step 4: Compare 5 vs 4 -> pick 4
  dummy -> 1 -> 2 -> 3 -> 4
  B moves to 6

Step 5: Compare 5 vs 6 -> pick 5
  dummy -> 1 -> 2 -> 3 -> 4 -> 5
  A is now NULL

Step 6: Append remaining B
  dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Return dummy.next

Finding the Middle Node (ASCII):

1 -> 2 -> 3 -> 4 -> 5 -> NULL

slow=1, fast=1

Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: fast.next is NULL -> stop

Middle node = slow = 3

Hint System

Problem 1: Reverse a Linked List (Easy)

Problem: Given the head of a singly linked list, reverse the list and return the new head.

Hints:

• Level 1: "Think about what needs to change for each node. Where does its next pointer currently point? Where should it point after reversal?"
• Level 2: "You need three pointers: one for the previous node, one for the current node, and one to save the next node before you overwrite it."
• Level 3: "Initialize prev = NULL, curr = head. At each step: save next = curr.next, then set curr.next = prev, then advance prev = curr, curr = next."
• Level 4:

  prev = None
  curr = head
  while curr:
      next_node = curr.next
      curr.next = prev
      prev = curr
      curr = next_node
  return prev
  

Problem 2: Detect a Cycle (Easy-Medium)

Problem: Given the head of a linked list, determine if the list has a cycle.

Hints:

• Level 1: "If you keep walking through the list forever, what does that tell you? How could two walkers moving at different speeds help?"
• Level 2: "Use two pointers: one moves one step at a time (slow), the other moves two steps (fast). What happens if there is a cycle?"
• Level 3: "If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet. If there is no cycle, the fast pointer will reach NULL."
• Level 4:

  slow = head
  fast = head
  while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow == fast:
          return True
  return False
  

Problem 3: Merge Two Sorted Lists (Easy-Medium)

Problem: Given two sorted linked lists, merge them into one sorted list.

Hints:

• Level 1: "Think about how you would merge two sorted arrays. The same comparison logic applies here."
• Level 2: "Create a dummy head node so you do not have to special-case the first element. Use a tail pointer that always points to the last node in your merged list."
• Level 3: "Compare the heads of both lists. Whichever is smaller, attach it to tail.next and advance that list's pointer. When one list is exhausted, attach the rest of the other."
• Level 4:

  dummy = ListNode(0)
  tail = dummy
  while l1 and l2:
      if l1.val <= l2.val:
          tail.next = l1
          l1 = l1.next
      else:
          tail.next = l2
          l2 = l2.next
      tail = tail.next
  tail.next = l1 if l1 else l2
  return dummy.next
  

Evaluation Rubric

Resources

Essential Practice

• LeetCode 206: Reverse Linked List
• LeetCode 141: Linked List Cycle
• LeetCode 21: Merge Two Sorted Lists
• LeetCode 876: Middle of the Linked List
• LeetCode 19: Remove Nth Node From End of List
• LeetCode 234: Palindrome Linked List
• LeetCode 143: Reorder List

Study Materials

• "Grokking the Coding Interview" - Linked List Reversal & Fast/Slow Pointers sections
• NeetCode.io - Linked List playlist
• Blind 75 list - Linked List section

If Candidate Struggled

• Practice drawing pointer diagrams on paper before coding
• Start with LeetCode 206 (Reverse Linked List) until it is second nature
• Review how memory and references work in their language of choice

If Candidate Aced Everything

• LeetCode 25: Reverse Nodes in k-Group
• LeetCode 23: Merge k Sorted Lists
• LeetCode 138: Copy List with Random Pointer

Sample Session

You: "Welcome! Let's start with a quick warm-up. Can you tell me what a singly linked list is and how it differs from an array?"

Candidate: "A linked list is a bunch of nodes connected by pointers. An array is contiguous memory."

You: "Good start. One key difference is that arrays give you O(1) random access by index, while a linked list requires O(n) traversal. But linked lists have an advantage for insertions at the head. What's the time complexity of inserting at the head of a linked list?"

Candidate: "O(1)?"

You: "Exactly right. Now, let's try a classic problem. Given a singly linked list, reverse it in place. Take a moment to think about what needs to happen to each node's pointer."

[Continue session...]

Interviewer Notes

• Pointer manipulation is one of the most visually confusing topics for beginners -- always offer to draw diagrams
• If a candidate gets lost mid-reversal, pause and trace through the current state of all three pointers (prev, curr, next)
• Common mistakes to watch for: forgetting to save the next pointer before overwriting it, returning the wrong node as the new head, not handling NULL/empty list
• If they ace Reverse and Cycle Detection, challenge them with Reorder List (combines finding middle, reversing, and merging)
• Celebrate incremental progress: "You got the iterative reversal -- want to try it recursively?"
• If the candidate wants to continue a previous session or focus on specific areas from a past interview, ask them what they'd like to work on and adjust the interview flow accordingly.

Additional Resources

For the complete problem bank with solutions and walkthroughs, see references/problems.md. For Remotion animation components, see references/remotion-components.md.