本文主要是介绍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;}
};如果我的文章对你有所帮助，不妨给我个关注何点赞吧。
这篇关于Leetcode 86. 分隔链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
