题目内容

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

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

示例：

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

解题思路

copy别人的打趣段子：天晴了雨停了我又觉得我行了。
使用两个链表一个记录小于x元素，一个记录大于x的元素，将第二个链表加在第一个的尾部得到结果。有这样一个简单的思路解题不难。
关键在于细节的空指针与越界异常处理。

解题代码

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* n1=nullptr,*n2=nullptr;
        ListNode *res=nullptr;ListNode *t=nullptr;
        while(head!=NULL)
        {
            if(head->val<x)
            {
                if(n1){n1->next=new ListNode;n1=n1->next;n1->val=head->val;n1->next=nullptr;}
                else {res=n1=new ListNode;res->val=head->val;res->next=nullptr;}
            }
            else
            {
                if(n2){n2->next=new ListNode;n2=n2->next;n2->val=head->val;n2->next=nullptr;}
                else {t=n2=new ListNode;t->val=head->val;t->next=nullptr;}
            }
            head=head->next;
        }
        if(!res)return t;
        n1->next=t;return res;
    }
};