2019 年第 41 题

题目描述

给定一个单链表 L0 -> L1 -> ... -> Ln-1 -> Ln，请将其重排为：

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

要求在原链表上完成重排。

解题思路

标准做法分三步：

1. 用快慢指针找到链表中点。
2. 反转后半段链表。
3. 将前半段和反转后的后半段交替合并。

这是 408 链表综合题中非常典型的一道。

手算示例

链表：1 -> 2 -> 3 -> 4 -> 5

1. 找中点
前半段：1 -> 2 -> 3
后半段：4 -> 5

2. 反转后半段
5 -> 4

3. 交替合并
1 -> 5 -> 2 -> 4 -> 3

Python 实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reorder_list(head):
    if head is None or head.next is None:
        return head

    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    second = slow.next
    slow.next = None

    prev = None
    cur = second
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    second = prev

    first = head
    while second:
        n1 = first.next
        n2 = second.next
        first.next = second
        second.next = n1
        first = n1
        second = n2

    return head

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

易错点

• 找到中点后要断开前后两段，否则可能形成环。
• 反转后半段时要先保存后继结点。
• 交替合并时每一步都要先存 next 指针。

对应题

来源	题目	相似度	主要差异
LeetCode	143. 重排链表	100%	基本一致

难度

⭐️⭐️⭐️