LeetCode 206: Reverse Linked List (Iterative + Recursive)
LeetCode 206Linked ListPointersRecursionToday we solve LeetCode 206 - Reverse Linked List, one of the most fundamental pointer manipulation problems.
Source: https://leetcode.com/problems/reverse-linked-list/
English
Problem Summary
Given the head of a singly linked list, reverse the list and return the new head. For example, 1 -> 2 -> 3 -> null should become 3 -> 2 -> 1 -> null.
Key Insight
Every node points forward. Reversal means making each node point backward. The safest way is to carry three pointers:
prev (already reversed part), curr (current node), and next (saved original next node so we don't lose the rest).
Brute Force and Why Insufficient
A naive idea is to copy values into an array, then rewrite the list from back to front. That costs O(n) extra space and doesn't practice true pointer reversal. Interviewers usually expect in-place reversal with O(1) extra space.
Optimal Algorithm (Step-by-Step)
Iterative in-place reversal:
1) Initialize prev = null, curr = head.
2) While curr != null:
a) Save next = curr.next.
b) Reverse link: curr.next = prev.
c) Move pointers: prev = curr, curr = next.
3) When loop ends, prev is the new head.
Complexity Analysis
Time: O(n) (visit each node once).
Space: O(1) for iterative solution.
Common Pitfalls
- Forgetting to store next before changing curr.next, causing list loss.
- Returning curr at the end instead of prev.
- Not handling edge cases: empty list or single node.
- Recursive version may overflow call stack for very long lists.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var prev *ListNode = nil
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};中文
题目概述
给定单链表头节点 head，请将链表反转并返回新的头节点。比如 1 -> 2 -> 3 -> null 反转后应为 3 -> 2 -> 1 -> null。
核心思路
链表反转的本质是“把每个节点的指针方向反过来”。为了不丢链，需要三个指针：
prev（已反转部分头部）、curr（当前处理节点）、next（先保存原始后继）。
暴力解法与不足
一种“伪暴力”思路是先把值拷贝到数组，再倒序写回链表。虽然时间是 O(n)，但额外空间也是 O(n)，并且没有真正训练指针操作。面试通常要求原地反转、O(1) 额外空间。
最优算法（步骤）
迭代原地反转：
1）初始化 prev = null，curr = head。
2）当 curr != null 时循环：
a）先保存 next = curr.next；
b）反转指针：curr.next = prev；
c）整体前进：prev = curr，curr = next。
3）循环结束后，prev 就是新头节点。
复杂度分析
时间复杂度：O(n)（每个节点访问一次）。
空间复杂度：O(1)（迭代写法仅常数额外空间）。
常见陷阱
- 没有先保存 next 就改 curr.next，导致后半链表丢失。
- 最后返回了 curr 而不是 prev。
- 忽略空链表、单节点链表边界情况。
- 递归方案在极长链表上可能栈溢出。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var prev *ListNode = nil
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};
Comments