Master pointer manipulation: slow/fast pointers, dummy head nodes, and in-place list reversal. These appear constantly in interviews.
Problems: 11
Easy: 3
Medium: 6
Hard: 2
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
Key idea: Dummy head eliminates null-checks for the result head. Compare front nodes of both lists, attach the smaller, advance that list's pointer. Append whichever list isn't exhausted.
find middle (slow/fast)reverse second halfmerge two halves
Split the list at the middle. Reverse the second half. Then interleave nodes from both halves.
Python Solution
def reorderList(head):
# 1. Find the middle using slow/fast pointers
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. Reverse the second half
prev, curr = None, slow.next
slow.next = None # cut the list
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# 3. Interleave the two halves
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2
Key idea: Three steps: (1) find the midpoint with slow/fast pointers, (2) reverse the second half, (3) interleave nodes from both halves.
Use two pointers with a gap of n+1 between them. When the fast pointer hits the end, the slow pointer is just before the node to remove.
Python Solution
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
# Advance fast by n+1 steps
for _ in range(n + 1):
fast = fast.next
# Move both until fast reaches end
while fast:
fast = fast.next
slow = slow.next
# slow is now just before the node to remove
slow.next = slow.next.next
return dummy.next
Key idea: Create a gap of n+1 between fast and slow pointers (using a dummy head). When fast reaches the end (None), slow is exactly at the predecessor of the nth-from-last node.
A linked list where each node has a random pointer. Make a deep copy. Return the head of the copied list.
Test Cases
Input: Node(7)→Node(13)→Node(11)..., random pointers
Output: Deep copy with same structure
old_to_new hash maptwo-passO(n) space
First pass: create all new nodes (without connections). Second pass: assign next and random pointers using the mapping.
Python Solution
class Node:
def __init__(self, x, next=None, random=None):
self.val = x
self.next = next
self.random = random
def copyRandomList(head):
if not head:
return None
# Map old node → new node
old_to_new = {None: None}
curr = head
while curr:
old_to_new[curr] = Node(curr.val)
curr = curr.next
# Set next and random using the map
curr = head
while curr:
old_to_new[curr].next = old_to_new[curr.next]
old_to_new[curr].random = old_to_new[curr.random]
curr = curr.next
return old_to_new[head]
Key idea: First pass creates all new nodes. Second pass wires up next and random using the old→new mapping. Including None→None in the map avoids null checks.
Add digit by digit. Keep track of a carry. Create a new node for each digit sum % 10. Don't forget a final carry node.
Python Solution
def addTwoNumbers(l1, l2):
dummy = ListNode(0)
curr = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
total = v1 + v2 + carry
carry = total // 10
curr.next = ListNode(total % 10)
curr = curr.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
Key idea: Simulate the addition column by column (digit by digit). Handle the carry. The loop continues while there's any remaining input or carry. A dummy head simplifies code.
Use a slow pointer (1 step) and a fast pointer (2 steps). If they ever meet, there's a cycle. Why is this guaranteed to work?
Python Solution
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Key idea: Floyd's cycle detection. The fast pointer laps the slow pointer inside the cycle — they must eventually point to the same node. If fast reaches None, there's no cycle.
Floyd's on index-as-pointerimplicit linked listO(n) O(1)
Treat each value as a pointer to an index. If there's a duplicate, the 'linked list' formed has a cycle. Use Floyd's algorithm.
Python Solution
def findDuplicate(nums):
# Phase 1: find intersection point inside the cycle
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: find entry point of the cycle (the duplicate)
slow2 = nums[0]
while slow != slow2:
slow = nums[slow]
slow2 = nums[slow2]
return slow
Key idea: Map value → index to create an implicit linked list. A duplicate means two indices point to the same next node, creating a cycle. Floyd's detects the cycle; the entry point is the duplicate.
Design a data structure implementing LRU cache. get(key) returns value or -1. put(key, value) inserts/updates. Evict the least recently used when capacity is exceeded.
An OrderedDict maintains insertion order. 'Recently used' = move to end. 'Least recently used' = the front item.
Python Solution
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False) # evict LRU (front)
Key idea: Python's OrderedDict remembers insertion order. Move items to the end on access/update. Evict from the front when over capacity.
Time: O(1) for both operations. Space: O(capacity).
Use a min-heap to always efficiently pick the smallest current head among all k lists. Push the next node from that list after popping.
Python Solution
import heapq
def mergeKLists(lists):
dummy = ListNode(0)
curr = dummy
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Key idea: A min-heap of size k stores the current front of each list. Pop the minimum, attach to result, then push that list's next node. The index i breaks ties so ListNode objects don't need comparison.
Time: O(n log k) — n total nodes, k-size heap. Space: O(k).
check k nodes aheadin-place reverse krecursive tail
First check if at least k nodes remain. If so, reverse k nodes in place, then recurse on the rest and connect.
Python Solution
def reverseKGroup(head, k):
# Check if at least k nodes remain
node = head
for _ in range(k):
if not node:
return head # fewer than k nodes, return unchanged
node = node.next
# Reverse k nodes
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head is now the tail of the reversed group
# recurse for the rest
head.next = reverseKGroup(curr, k)
return prev # prev is the new head of this group
Key idea: Check k nodes exist, reverse them in place, then recursively handle the remainder. After reversing, the original head becomes the tail of the group, so connect it to the recursive result.