[LeetCode/力扣][C++] 86. 分隔链表（Partition List）

题目描述（中等）：

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

示例1：

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

思路： 遍历整个链表，若当前节点值 $<$ x则将其移至首个 $\ge$ x的节点的左侧。相当于把整个列表视为两部分：大于等于x和小于x，利用四个分别指向两部分头和尾的指针来进行标记。若当前节点 $<$ x，则将其插入到较小链表最左侧与较大链表最右侧之间。此外还有些特殊情况需要处理，当结点个数 $<$ 2 以及 链表节点值均 $\ge$ x or $<$ x时，输出头结点即可。

代码：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* cur = head;
        ListNode* lowL = NULL;      //较小链表头结点
        ListNode* lowR = lowL;      //较小链表尾部
        ListNode* highL = NULL;     //较大链表头结点
        ListNode* highR = highL;    //较大链表尾部
        if (head->val < x) lowL = head;
        else highL = head;
        while (cur) {
            if (cur->val < x) { //找到第一个小于x的节点
                if (lowL == NULL) {lowL = cur;lowR = lowL;}
                else lowR = cur;
            }
            else {
                highL = cur;
                highR = highL;
                break;
            }
            cur = cur->next;
        }
        if (highL == NULL) return head; //由于找到第一个大于等于x的节点就跳出循环，因此不能判断lowL为空时返回头节点
        //cur指向第一个大于等于x的节点的左侧
        cur = cur->next;
        while (cur) {
            if (cur->val < x) {
                ListNode* temp = cur->next;
                if (lowL == NULL) { //当前第一个节点为x
                    cur->next = highL;
                    highR->next = temp;
                    lowL = cur;     //保证lowL返回时为头结点
                    lowR = lowL;
                    cur = temp;
                    //continue;
                } else {
                    lowR->next = cur;
                    cur->next = highL;
                    lowR = cur;
                    highR->next = temp;
                    cur = temp;
                    //continue;
                }
            } else {
                highR = cur;
                cur = cur->next;
            }
        }
        if (lowL == NULL) return head;
        else return lowL;
    }
};
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

AC后还没看评论区大佬的代码和思路，但肯定比我厉害多了。