本文共 1422 字，大约阅读时间需要 4 分钟。

题目：86. 分隔链表

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

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

示例：

输入：head = 1->4->3->2->5->2, x = 3

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/partition-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

构造两个指针分别连接小于x的节点和大于等于x的节点，最后再串起来。

代码

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    ListNode* partition(ListNode* head, int x) {
           ListNode* big = NULL;        ListNode* bigHead = NULL;        ListNode* little = NULL;        ListNode* littleHead = NULL;        while(head) {
               if(head->val < x) {
                   if(!little) {
                       little = head;                    littleHead = head;                } else {
                       little->next = head;                    little = little->next;                }            } else {
                   if(!big) {
                       big = head;                    bigHead = head;                } else {
                       big->next = head;                    big = big->next;                }            }            head = head->next;        }        if (big) {
               big->next = NULL;        }        if(little) {
               little->next = bigHead;            return littleHead;        }        return bigHead;    }};