leetcode86. 分隔链表

分析

利用尾插法，将链表分为两条，一条比x大，另一条比x小，最后两个链表再合并。

/**
 * 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 {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummya=new ListNode();
        ListNode* dummyb=new ListNode();
        ListNode* taila=dummya,*tailb=dummyb;
        ListNode* cur=head;
        while(cur){
            if(cur->val<x){
               taila->next=cur;
               taila=cur;
               cur=cur->next;
               taila->next=nullptr;
            }else{
                tailb->next=cur;
                tailb=cur;
                cur=cur->next;
                tailb->next=nullptr;
            }
        }
        taila->next=dummyb->next;
        return dummya->next;
    }
};