反转链表
使用三个指针重新连接节点，以迭代和递归方式反转单链表，并在白板风格的图示中跟踪每一步。
反转链表 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
为什么链表反转至关重要
反转链表是编码面试中最常见的问题之一。它检验您能否精确操作指针，同时不丢失对节点的跟踪。它的变体既会作为独立问题出现，也会作为更大型算法的子步骤出现，例如回文检测、链表重排和 k 组反转。
迭代方法使用三个指针：prev、curr 和 next_node。递归方法则将相同的逻辑表达为调用栈遍历。两种方法的时间复杂度均为 O(n)，而迭代方法的空间复杂度为 O(1)。
三指针迭代反转
在迭代反转的每一步中：保存 curr.next，以免丢失链表的其余部分；将 curr.next 翻转为指向 prev；将 prev 向前移动到 curr；再将 curr 向前移动到保存的下一个节点。当 curr 变为 None 时，循环结束，此时 prev 就是新的头节点。
一个实用的记忆口诀是：保存、翻转、前进、前进。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save
curr.next = prev # Flip
prev = curr # Advance prev
curr = next_node # Advance curr
return prev # new head
# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
print(head.val, end=' ') # 5 4 3 2 1
head = head.next逐步跟踪
让我们跟踪 reverse_list 处理 1 -> 2 -> 3 的过程。初始状态为 prev=None, curr=1。第 1 步：保存下一个节点为 2，将节点 1 指向下一个节点的指针翻转为 None，前驱节点为 1，当前节点为 2。第 2 步：保存下一个节点为 3，将节点 2 指向下一个节点的指针翻转为 1，前驱节点为 2，当前节点为 3。第 3 步：保存下一个节点为空，将节点 3 指向下一个节点的指针翻转为 2，前驱节点为 3，当前节点为空。循环结束；返回节点 3，它是 3 -> 2 -> 1 的新头节点。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_traced(head):
prev, curr = None, head
step = 0
while curr:
step += 1
next_node = curr.next
curr.next = prev
print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
prev = curr
curr = next_node
return prev
nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val) # 3递归反转
递归方法依赖这样一个前提：reverse_list(head.next) 会返回已经反转的后缀链表的新头节点。剩下要做的就是翻转 head 与 head.next 之间的指针：设置 head.next.next = head（让原来的第二个节点指回原来的第一个节点），并设置 head.next = None（断开原来的正向链接）。新头节点会从基本情况逐层向上返回。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_rec(head):
# Base case: empty or single node
if not head or not head.next:
return head
new_head = reverse_list_rec(head.next) # reverse suffix
head.next.next = head # former second node points back
head.next = None # sever forward link
return new_head
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
print(head.val, end=' ') # 4 3 2 1
head = head.next反转子链表（LeetCode 92）
LeetCode 92《反转链表 II》要求您在一次遍历中，将从左侧位置到右侧位置的子链表反转（位置从 1 开始编号）。关键是找到子链表前面的节点（使用哑头节点即可确保这一点始终有效），然后准确执行（右侧位置 − 左侧位置）次三指针反转，最后将反转后的片段重新连接到周围的链表。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(head, left, right):
dummy = ListNode(0, head)
pre = dummy
# Advance pre to node just before position 'left'
for _ in range(left - 1):
pre = pre.next
curr = pre.next
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = pre.next
pre.next = next_node
return dummy.next
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
print(head.val, end=' ') # 1 4 3 2 5
head = head.nextK 组反转节点（LeetCode 25）
LeetCode 25《K 组反转节点》会反转每个连续的 k 个节点分组。具体方法是：先检查是否还剩 k 个节点；如果不足 k 个，就保持它们原来的顺序。使用迭代方法反转接下来的 k 个节点，然后递归反转剩余链表并将其连接起来。时间复杂度仍为 O(n)，递归调用深度为 O(n/k)。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseKGroup(head, k):
# Check if k nodes are available
curr, count = head, 0
while curr and count < k:
curr = curr.next
count += 1
if count < k:
return head # fewer than k nodes left, keep as-is
# 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
head.next = reverseKGroup(curr, k)
return prev
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
print(head.val, end=' ') # 2 1 4 3 5
head = head.next回文链表
LeetCode 234《回文链表》要求您判断链表是否为回文，时间复杂度为 O(n)，空间复杂度为 O(1)。策略是：使用慢速和快速指针找到中点，在原链表中反转后半部分，逐节点比较两部分，然后根据需要恢复链表。这个过程将寻找中点和反转结合起来，这是两项基础技能。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head):
# Find mid
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
def build(arr):
d = ListNode(0)
c = d
for v in arr:
c.next = ListNode(v)
c = c.next
return d.next
print(isPalindrome(build([1,2,2,1]))) # True
print(isPalindrome(build([1,2,3]))) # False迭代与递归对比
迭代反转使用 O(1) 空间，通常更受推荐。递归反转由于调用深度会使用 O(n) 栈空间，对于非常长的链表可能导致栈溢出（Python 的默认限制约为 1000 个递归层级）。
在面试中，请先实现迭代版本，以展示您对空间限制的理解；如果链表长度有上限，再将递归版本作为更简洁的替代方案提出。
import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint
# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)反转中的常见错误
几乎所有反转错误都源于三种失误。第一，覆盖前没有保存下一个节点：如果没有保存 next_node，curr.next = prev 就会破坏向前的引用。第二，没有返回前驱节点：循环结束时，curr 是 None，而 prev 才是新头节点。第三，递归基本情况错误：忘记检查 not head.next 会导致单节点链表无法处理，并引发 AttributeError。
# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # BUG if omitted: lose rest of list
curr.next = prev
prev = curr
curr = next_node
return prev # BUG if you return curr: it is None
nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
print(h.val, end=' ') # 3 2 1
h = h.next重排链表（LeetCode 143）
LeetCode 143《重排链表》会将 L0 → L1 → L2 → ... → Ln 重新排列为 L0 → Ln → L1 → Ln-1 → L2 → Ln-2，时间复杂度为 O(n)，空间复杂度为 O(1)。解决方案分为三个步骤：找到中点、反转后半部分，以及交错合并两部分。掌握反转后，这道看似复杂的问题就会变成几个熟悉工具的直接组合。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
if not head or not head.next:
return
# Find mid
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Interleave
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
print(h.val, end=' ') # 1 4 2 3
h = h.next总结：反转是基础模块
链表反转很少是最终目标——它是一个基础模块。回文检测、K 组反转、重排链表，以及按位置反转，都依赖同一种三指针迭代模式。一旦能够熟练运用这一模式，您就可以将思考精力集中在更高层次的问题结构上。
请一直练习反转，直到您能够在两分钟内凭记忆写出代码；在几乎每一轮链表面试中，它都会以某种形式出现。
快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学到了：迭代式的保存—翻转—前进—前进模式可以在 O(n) 时间和 O(1) 空间内反转链表，递归方法依赖后缀已经反转这一前提，只需修正最后一个链接，以及反转是回文检测、重排链表和 K 组反转中的核心子步骤。接下来，我们将使用弗洛伊德算法探索环检测。
常见问题解答
「反转链表」课时是免费的吗？
是的 — 「反转链表」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「反转链表」这节课中我会学到什么？
使用三个指针重新连接节点，以迭代和递归方式反转单链表，并在白板风格的图示中跟踪每一步。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「反转链表」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。