Leetcode 86. 分隔链表

题目链接：

86. 分隔链表 - 力扣（LeetCode）https://leetcode.cn/problems/partition-list/description/

题目：

给你一个链表的头节点 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

思路：

实现读题，题目要求我们将链表节点val值小于目标值x的节点放在第一个大于或等于x值的节点前。(一开始做这题我看成了将val值小于x的节点放在大于该val值前，害的我WA了好几次，所以说要好好读题)

那么我们可以设置两种头节点(big_head和small_head)分别用于存储val值大于等于x的节点和val值小于x的节点。再设置一个指针now指向head节点，表示当前指向的节点；一个指针small指向val值小于x的链表尾部(small_head)；一个指针big指向val大于等于x的链表尾部(big_head)。

接着循环遍历每个节点即可，让val值大于等于x的节点接在big后，然后让big指向big的下一个节点；让val值小于x的节点接在small后，然后让small指向small的下一个节点即可。

最后，让small的next指向big_head的下一个节点(即重新连接两个链表变成一个链表)，返回指针small_head的next指向的地址即可。

AC代码：

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* big_head = new ListNode(0);
        ListNode* small_head = new ListNode(0);
        ListNode* big = big_head;
        ListNode* small = small_head;
        ListNode* now = head;
        while (now != nullptr) {
            if (now->val < x) {
                small->next = now;
                small = small->next;
            }
            else {
                big->next = now;
                big = big->next;
            }
            now = now->next;
        }
        small->next = big_head->next;
        big->next = nullptr;
        return small_head->next;
    }
};

如果我的文章对你有所帮助，不妨给我个关注何点赞吧。