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

题目描述

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

来源：力扣（LeetCode）

/** * Definition for singly-linked list. * 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 {
       /*类似与一次划分，那就用双指针,不用改指针指向，只改值    上边的思路不行，因为要保证之前的相对位置，    新开链表,一个链表放小于X的节点，一个链表放大于X的节点，再拼接    */public:    ListNode* partition(ListNode* head, int x) {
           if(!head)  return head;               ListNode * small_head=new ListNode(0);        ListNode * p=small_head;// 存放小于x的节点        ListNode* big_head=new ListNode(0);        ListNode* q=big_head;        while(head){
               if(head->val
   
    next=head;                p=p->next;            }                        else{
                       q->next=head;                    q=q->next;                }                          head=head->next;            }        p->next=big_head->next;        q->next=nullptr;        return small_head->next;    }};