【LetMeFly】86.分隔链表

力扣题目链接：https://leetcode.cn/problems/partition-list/

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

 

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

 

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

方法一：双指针

这一题我们只需要把原始链表依据“是否小于x”的规则分成两个链表，再把两个链表合并即可。

首先定义两个新的头节点，遍历原始链表，把每个节点分别添加到新的对应的链表中。

最后，把“小于x的链表”的最后一个节点的next指向“大于等于x的链表”的第一个节点，把“大于等于x的链表”的最后一个节点的next置空，返回“小于x的链表”的第一个节点即可。

具体实现可详见代码注释。

• 时间复杂度$O(N)$，其中$N$是原始链表的节点个数
• 空间复杂度$O(1)$，只需要常数个节点（把节点添加到链表尾部只需要修改next指针，并不需要额外的空间）

AC代码

C++

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* le = new ListNode, *ge = new ListNode;  // 小于x的链表、大于等于x的链表
        ListNode* p1 = le, *p2 = ge;  // 两个指针
        while (head) {  // 遍历原始链表
            if (head->val < x) {
                p1->next = head;  // 添加到“小于x的链表”后面
                p1 = p1->next;  // 指针后移
            }
            else {
                p2->next = head;  // // 添加到“大于等于x的链表”后面
                p2 = p2->next;
            }
            head = head->next;
        }
        p1->next = ge->next;  // “小于x的链表”的最后一个节点指向“大于等于x的链表”的第一个节点（头节点为空，并未存储值，因此指向ge->next）
        p2->next = nullptr;  // “大于等于x的链表”的最后一个节点的next置空
        return le->next;  // 返回“小于x的链表”的第一个节点
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125467594