合并、拆分与查找倒数第 N 个节点
以 O(n) 的时间合并两个有序链表，使用快慢指针在中点拆分链表，并找出倒数第 n 个节点。
合并、拆分与查找倒数第 N 个节点 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
三种必备链表模式
本课介绍三种基础链表操作，它们经常作为更复杂问题的基础模块出现：合并两个有序链表（用于归并排序和 K 路合并）、在链表中点处拆分链表（用于归并排序和回文检测），以及寻找倒数第 n 个节点（用于删除倒数第 n 个节点）。
这三种操作都依赖您已经见过的技术：哑头节点、慢速和快速指针，以及对边界的谨慎跟踪。
合并两个有序链表
LeetCode 21《合并两个有序链表》：给定两个有序链表，返回一个合并后的有序链表。请使用哑头节点和 curr 尾指针。每一步都比较两个链表的头节点，并将较小的节点连接到 curr。当其中一个链表耗尽时，将另一个链表的剩余部分连接起来。时间复杂度：O(n+m)；空间复杂度：O(1)（原地重连）。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))逐步跟踪合并过程
跟踪 mergeTwoLists([1,2,4], [1,3,4])：比较 1 和 1——选择第一条链表中的 1，将第一条链表前进到 2。比较 2 和 1——选择第二条链表中的 1，将第二条链表前进到 3。比较 2 和 3——选择第一条链表中的 2，将第一条链表前进到 4。比较 4 和 3——选择第二条链表中的 3，将第二条链表前进到 4。比较 4 和 4——选择第一条链表中的 4，将第一条链表前进到空值。连接第二条链表中剩余的 4。结果：[1,1,2,3,4,4]。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))使用慢速和快速指针寻找中点
要在链表中点处拆分链表，请使用慢速和快速指针模式。slow 前进 1 步；fast 前进 2 步。当 fast 到达 None（或最后一个节点）时，slow 就位于中点。对于偶数长度的链表，这会得到两个中间节点中的第一个，这也是归并排序拆分链表时的常用方式。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]链表上的归并排序
LeetCode 148“排序链表”：在 O(n log n) 时间和 O(log n) 空间内对链表进行排序。方法是：在中点处分割链表，递归地对两半分别排序，然后进行合并。链表归并排序很自然，因为在中点处分割链表需要 O(n) 时间（不像数组那样是 O(1)），但整体复杂度仍为 O(n log n)，且只需要 O(log n) 的栈空间。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]查找倒数第 N 个节点
LeetCode 19“移除链表倒数第 N 个节点”：一次遍历找到从链表尾部开始数的第 n 个节点。使用两个相隔恰好 n 个节点的指针。让 fast 比 slow 先前进 n 步。然后同时移动两个指针，直到 fast 到达最后一个节点。此时，slow 位于倒数第 (n+1) 个节点处，也就是待删除节点的前驱节点。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]移除倒数第 N 个节点时为何要前进 n+1 步
关键细节是：从虚拟头节点开始，让快指针前进 n+1 步，而不是 n 步。前进 n+1 步后，快指针比慢指针领先 n+1 个位置（两者都从虚拟头节点开始）。当快指针到达空值时，慢指针位于空值之前 n+1 个位置，这意味着慢指针从零开始计数时位于位置（链表长度 - n - 1），也就是目标节点的前驱节点。这样就可以通过 slow.next = slow.next.next 干净地删除倒数第 n 个节点。
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')两个链表的相交节点
LeetCode 160“两个链表的相交节点”：找到两个链表首次相交的节点。这个 O(1) 空间技巧是：为每个链表设置一个指针。当某个指针到达空值时，将它重定向到另一个链表的头节点。经过至多“链表 A 的长度 + 链表 B 的长度”步后，两个指针走过的总距离相同，因此必定会在相交节点处相遇；如果没有相交，它们则都会到达空值。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8合并 K 个有序链表（分治法）
LeetCode 23“合并 K 个有序链表”：给定 k 个有序链表，将它们合并为一个链表。最优方法是使用分治法反复合并链表对，每轮将链表数量减半。对于 k 个平均长度为 n 的链表，这种方法的时间复杂度为 O(n k log k)，而顺序合并的复杂度为 O(n k²)。使用最小堆的方法同样是 O(n k log k)。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]奇偶链表
LeetCode 328“奇偶链表”：先将所有奇数索引节点排列在前，再排列偶数索引节点（索引从 1 开始计数）。方法是：维护两条独立的链（奇数链和偶数链），完成后将它们连接起来。遍历链表一次即可，因此时间复杂度为 O(n)，空间复杂度为 O(1)。这是一个同时以不同步长移动两个指针的简洁示例。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]综合运用
本课中的三种模式——合并有序链表、在中点处分割链表、查找倒数第 n 个节点——有一个共同主题：使用额外的指针变量跟踪位置，而不需要额外的内存。虚拟头节点简化了合并和删除操作；快慢指针之间的间距固定了特定的相对位置；先移动一个指针则可以创建所需的间隔。
在面试中，请在编写代码前说出您使用的模式：“我将使用双指针间隔技巧，在一次遍历中找到倒数第 n 个节点。”这能体现您条理清晰的思考方式。
快速检查
请测试您对本课“数据结构与算法——编程面试准备”概念的理解。
课程回顾
在本课中，您学习了：合并两个有序链表时使用虚拟头节点，并在每一步进行比较，从而达到 O(n+m) 时间和 O(1) 空间；在中点处分割链表时使用快慢指针，并让快指针停在最后一个有效节点对处；以及查找倒数第 n 个节点时，让快指针先前进 n+1 步，使慢指针落在目标节点的前驱处。接下来，我们将构建栈和队列，并把它们应用于经典的面试问题。
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「合并、拆分与查找倒数第 N 个节点」课时是免费的吗？
是的 — 「合并、拆分与查找倒数第 N 个节点」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「合并、拆分与查找倒数第 N 个节点」这节课中我会学到什么？
以 O(n) 的时间合并两个有序链表，使用快慢指针在中点拆分链表，并找出倒数第 n 个节点。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「合并、拆分与查找倒数第 N 个节点」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 节点类与链表构造
- 反转链表
- 使用 Floyd 算法检测环
- 合并、拆分与查找倒数第 N 个节点