The example problem
Given the head of a singly linked list, reverse the list and return the new head.
Input: 1 → 2 → 3 → 4 Output: 4 → 3 → 2 → 1
Picture it
A linked list is like a train: each coach holds a value and a coupling to the next coach. The only way in is the first coach (the head). To reverse it, we walk along with three markers: prev (the part already reversed), curr (the coach we’re fixing) and nxt (the rest of the train, remembered so we don’t lose it). For each coach we flip its coupling to point backwards.
The key idea
Remember next, point curr back at prev, then move both forward. O(n) time, O(1) extra space.
Python
def reverse(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevPractise linked list
- LeetCode 2Add Two NumbersTwo odometer trains, digit by digit
- LeetCode 19Remove Nth Node From End of ListTwo inspectors, n coaches apart
- LeetCode 21Merge Two Sorted ListsTwo sorted trains meeting at a junction
- LeetCode 24Swap Nodes in PairsSwapping coaches two at a time
- LeetCode 25Reverse Nodes in k-GroupReversing the train k coaches at a time
- LeetCode 86Partition ListSorting coaches onto two sidings
- LeetCode 92Reverse Linked List IIReversing only part of a train
- LeetCode 141Linked List CycleTortoise and hare on a looping track
- LeetCode 142Linked List Cycle IIWhere does the loop begin?
- LeetCode 138Copy List with Random PointerPhotocopying a train with buddy links
- LeetCode 160Intersection of Two Linked ListsTwo branch lines joining one track
- LeetCode 202Happy NumberA chain of number plates that may loop
- LeetCode 203Remove Linked List ElementsUncoupling every coach with one number
- LeetCode 234Palindrome Linked ListFolding a train in half
- LeetCode 237Delete Node in a Linked ListRemoving a coach you’re standing in
- LeetCode 328Odd Even Linked ListOdd coaches first, then even
- LeetCode 445Add Two Numbers IIAdding from the back with two plate stacks
NeetCode 150 problems that use it
Linked List ·
- LeetCode 206 · EasyReverse Linked ListRecoupling a train backwards
- LeetCode 21 · EasyMerge Two Sorted ListsTwo sorted trains meeting at a junction
- LeetCode 143 · MediumReorder ListZipping the front of a train with its back
- LeetCode 19 · MediumRemove Nth Node From End of ListTwo inspectors, n coaches apart
- LeetCode 138 · MediumCopy List with Random PointerPhotocopying a train with buddy links
- LeetCode 2 · MediumAdd Two NumbersTwo odometer trains, digit by digit
- LeetCode 141 · EasyLinked List CycleTortoise and hare on a looping track
- LeetCode 287 · MediumFind the Duplicate NumberBoxes with notes pointing to other boxes
- LeetCode 146 · MediumLRU CacheA small hotel that evicts the guest who’s been idle longest
- LeetCode 23 · HardMerge k Sorted ListsA dispatcher merging trains from k tracks
- LeetCode 25 · HardReverse Nodes in k-GroupReversing the train k coaches at a time