Reorder List

143. 重排链表

分析

第一步：找到链表的中点
- 遍历链表长度，再通过 (len + 1) / 2 找到中间节点位置
第二步：反转链表后半段
- 从中点开始，原地反转链表后半段
第三步：合并两段链表
- 将前半段和后半段反转后的链表进行交叉合并
- 注意尾指针的处理，避免无限循环

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


class Solution
{
public:
    void reorderList(ListNode* head)
    {
        if (!head) return;

        // 1. 统计链表长度
        int len = 0;
        for (ListNode* p = head; p; p = p->next)
            ++len;

        // 2. 找到链表中点
        ListNode* mid = head;
        for (int i = 0; i < (len + 1) / 2 - 1; ++i)
            mid = mid->next;

        // 3. 反转链表后半部分
        ListNode *a = mid, *b = mid->next;
        for (int i = 0; i < len / 2; ++i)
        {
            ListNode* c = b->next;
            b->next = a;
            a = b;
            b = c;
        }

        // 4. 合并两段链表
        ListNode *p = head, *q = a;
        for (int i = 0; i < len / 2; ++i)
        {
            ListNode* o = q->next;
            q->next = p->next;
            p->next = q;

            if (len % 2 == 0 && i == len / 2 - 1)
                q->next = nullptr;

            q = o;
            p = p->next->next;
        }

        if (len % 2 == 1)
            p->next = nullptr;
    }
};