重排链表 图解题解

这道题到底在问什么

示例

1→2→3→4→5 → 1→5→2→4→3

最优解：一步一步想明白

1. 3用数组存节点再重连可以做，但链表题重点是原地改指针。
2. 4快慢指针找中点，反转后半段，再一前一后交替插入。
3. 5slow=3, fast 到尾先用快慢指针找中点:fast 一次两步、slow 一次一步。fast 到尾时,slow 正好停在中间 3。从这里把链表劈成两半。
4. 6second: 5 → 4从中点断开:前半 1→2→3、后半 4→5。把后半段三指针反转(prev/cur/nxt 边走边掉头)→ 变成 5→4。
5. 7first: 1→2→3 · second: 5→4现在两条链对齐:前半 1→2→3、反转后的后半 5→4。接下来各取一个、交替穿插合并。
6. 8first.next=second, 再往后交替接线:1 的 next 接后半的 5,5 的 next 再接前半的 2 —— 1→5→2。每次从两条链各取一个,你一个我一个。
7. 9结果: 1→5→2→4→3继续交替到两条链取空:1→5→2→4→3。全程只改指针指向、不新建节点 → 原地完成,O(1) 额外空间。
8. 12一句话记住：快慢指针找中点，反转后半段，再一前一后交替插入。
9. 15忘断/忘记头 → 丢节点或成环雷区:① 劈两半时 slow.next 要置 null 断开前半尾,否则合并后成环;② 反转后半前先记住它的头。三步(找中点/反转/合并)指针多,顺序错就丢节点。
10. 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=linkedlist 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def reorderList(self, head):
        if not head or not head.next:
            return
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
        slow.next = None
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        first, second = head, prev
        while second:
            n1, n2 = first.next, second.next
            first.next = second
            second.next = n1
            first, second = n1, n2

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* second = slow->next;
        slow->next = nullptr;
        ListNode* prev = nullptr;
        while (second) {
            ListNode* nxt = second->next;
            second->next = prev;
            prev = second;
            second = nxt;
        }
        ListNode *first = head;
        second = prev;
        while (second) {
            ListNode *n1 = first->next, *n2 = second->next;
            first->next = second;
            second->next = n1;
            first = n1;
            second = n2;
        }
    }
};

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (second != null) {
            ListNode nxt = second.next;
            second.next = prev;
            prev = second;
            second = nxt;
        }
        ListNode first = head;
        second = prev;
        while (second != null) {
            ListNode n1 = first.next, n2 = second.next;
            first.next = second;
            second.next = n1;
            first = n1;
            second = n2;
        }
    }
}

# 1. 定义状态
state = init()
# 2. 按顺序读输入
for x in data:
    update(state, x)   # 只做本题允许的安全转移
# 3. 从状态里取答案
return answer(state)

// 1. init state
for (auto x : data) {
    // update state with the same invariant
}
return ans;

// 1. init state
for (int x : data) {
    // update state with the same invariant
}
return ans;

复杂度

面试官可能追问