分隔节点（C++解法）

解法）"/>

分隔节点（C++解法）

题目

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

C++代码

#include <iostream>
using namespace std;//创建链表结构体
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) {}
};/*
* 分隔链表问题
* 定义small链表存放元链表中比x小的节点，large链表存放大于等于x的节点
* 并定义两个链表的虚拟头节点，防止头节点为空的情况
* 条件判断分隔节点，合并为结果链表
*/
ListNode* partition(ListNode* head, int x) {ListNode* small = new ListNode(0);ListNode* smallHead = small;ListNode* large = new ListNode(0);ListNode* largeHead = large;while (head) {if (head->val < x) {small->next = head;small = small->next;}else {large->next = head;large = large->next;}head = head->next;}large->next = nullptr;small->next = largeHead->next;return smallHead->next;
}int main() {ListNode* n1 = new ListNode(1);ListNode* n2 = new ListNode(4);ListNode* n3 = new ListNode(3);ListNode* n4 = new ListNode(2);ListNode* n5 = new ListNode(5);ListNode* n6 = new ListNode(2);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = n6;n6->next = nullptr;ListNode* head = n1;int x = 3;ListNode* ans = partition(head, x);while (ans) {cout << ans->val << " ";ans = ans->next;}delete n1, n2, n3, n4, n5, n6;return 0;
}

分析

分隔链表问题，定义 small 链表存放元链表中比 x 小的节点，large 链表存放大于等于 x 的节点，并定义两个链表的虚拟头节点，防止头节点为空的情况，条件判断分隔节点，合并为结果链表。