Partition List

86. 分隔链表

分析

使用两个虚拟头节点 small_head 和 big_head 分别构建两条子链表：

遍历原链表，对于每个节点：
- 如果值小于 x，将该节点添加到以 small_head 为头的链表
- 如果值大于或等于 x，将该节点添加到以 big_head 为头的链表
遍历结束后，将小链表的尾部连接到大链表的头部
返回合并后的链表（从 small_head->next 开始）

时间复杂度

时间复杂度 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


class Solution
{
public:
    ListNode* partition(ListNode* head, int x)
    {
        // 初始化两个虚拟头节点和尾指针
        auto small_head = new ListNode(-1), big_head = new ListNode(-1);
        auto small_tail = small_head, big_tail = big_head;

        // 遍历链表，分隔节点
        for (auto p = head; p; p = p->next)
        {
            if (p->val < x)
                small_tail = small_tail->next = p; // 添加到小链表
            else
                big_tail = big_tail->next = p;    // 添加到大链表
        }

        // 合并两部分链表
        small_tail->next = big_head->next;
        big_tail->next = NULL; // 确保大链表尾部没有残留节点

        return small_head->next; // 返回分隔后的链表
    }
};