NeetCode 150 · Linked List

Linked List Problems

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.
01 Easy Linked ListRecursion
Given the head of a singly linked list, reverse the list and return the reversed list's head.
Test Cases
Input: 1→2→3→4→5 Output: 5→4→3→2→1 Input: 1→2 Output: 2→1
prev/curr/next tripleiterativeO(n) O(1)
Walk through the list. At each node, reverse its next pointer to point to the previous node. You need three pointers: prev, curr, next.
Python Solution
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseList(head): prev = None curr = head while curr: next_node = curr.next # save next curr.next = prev # reverse pointer prev = curr # advance prev curr = next_node # advance curr return prev
Key idea: Walk through the list once. At each node, save next_node, then point curr.next backward to prev. After the loop, prev is the new head.
Time: O(n).
Space: O(1).
02 Easy Linked ListRecursion
Merge two sorted linked lists and return the merged list. The merged list should be made by splicing together the nodes of the two lists.
Test Cases
Input: 1→2→4, 1→3→4 Output: 1→1→2→3→4→4
dummy headpointer comparisonO(m+n)
Use a dummy head to simplify edge cases. Compare the heads of both lists and attach the smaller one to the result.
Python Solution
def mergeTwoLists(list1, list2): dummy = ListNode(0) curr = dummy while list1 and list2: if list1.val <= list2.val: curr.next = list1 list1 = list1.next else: curr.next = list2 list2 = list2.next curr = curr.next curr.next = list1 or list2 # attach remaining return dummy.next
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.
Time: O(m+n).
Space: O(1).
03 Medium Linked ListTwo PointersStack
Given linked list L0→L1→…→Ln, reorder it to L0→Ln→L1→Ln-1→L2→Ln-2→… Modify in-place.
Test Cases
Input: 1→2→3→4 Output: 1→4→2→3 Input: 1→2→3→4→5 Output: 1→5→2→4→3
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.
Time: O(n).
Space: O(1).
04 Medium Linked ListTwo Pointers
Given head of a linked list, remove the nth node from the end and return the list's head. Do it in one pass.
Test Cases
removeNthFromEnd(1→2→3→4→5, 2) → 1→2→3→5 removeNthFromEnd(1, 1) → [] removeNthFromEnd(1→2, 1) → 1
dummy headfast pointer n+1 aheadone pass
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.
Time: O(n) — one pass.
Space: O(1).
05 Medium Linked ListHash Map
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.
Time: O(n).
Space: O(n).
06 Medium Linked ListMathRecursion
Two linked lists store digits of non-negative integers in reverse order. Add the two numbers and return the sum as a linked list.
Test Cases
Input: (2→4→3) + (5→6→4) [342 + 465] Output: 7→0→8 [807]
digit-by-digit additioncarrydummy head
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.
Time: O(max(m,n)).
Space: O(max(m,n)).
07 Easy Linked ListTwo PointersHash Table
Given head of a linked list, determine if the list has a cycle.
Test Cases
Input: 3→2→0→-4 (tail connects to node 1) Output: True Input: 1→2 (no cycle) Output: False
Floyd's cycle detectionslow/fast pointersO(n) O(1)
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.
Time: O(n).
Space: O(1).
08 Medium ArrayTwo PointersBinary Search
Given array of n+1 integers where each integer is in [1, n], find the one duplicate. Must use O(1) extra space, cannot modify array.
Test Cases
findDuplicate([1,3,4,2,2]) → 2 findDuplicate([3,1,3,4,2]) → 3
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.
Time: O(n).
Space: O(1).
09 Medium Hash MapLinked ListDesign
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.
Test Cases
cache = LRUCache(2) cache.put(1, 1); cache.put(2, 2) cache.get(1) → 1 cache.put(3, 3) # evicts key 2 cache.get(2) → -1
OrderedDictmove_to_endpopitem(last=False)
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).
10 Hard Linked ListHeapDivide and Conquer
Merge k sorted linked lists and return the merged sorted list.
Test Cases
Input: [[1,4,5],[1,3,4],[2,6]] Output: 1→1→2→3→4→4→5→6
min heap(val, i, node) tuplesO(n log k)
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).
11 Hard Linked ListRecursion
Given linked list, reverse every k nodes. If remaining nodes are fewer than k, leave them as is.
Test Cases
reverseKGroup(1→2→3→4→5, 2) → 2→1→4→3→5 reverseKGroup(1→2→3→4→5, 3) → 3→2→1→4→5
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.
Time: O(n).
Space: O(n/k) recursion depth.
← Prev Category Next Category →