86. 分隔链表

原题链接：86. 分隔链表

solution:

        ① 创建两个链表
        ② 链表1保存所有小于x的节点，链表2保存所有大于等于x的节点
        ③ 最后拼接两个链表

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode *dummy1 = new ListNode(-1);    //虚拟头结点1
        ListNode *dummy2 = new ListNode(-1);    //虚拟头结点2
        ListNode *cur1 = dummy1;
        ListNode *cur2 = dummy2;
        
        //链表1连接小于x的节点
        //链表2连接大于等于x的节点
        ListNode *tmp = head;
        while(tmp != nullptr) {
            if(tmp->val < x) {
                cur1->next = tmp;
                cur1 = cur1->next;
                tmp = tmp->next;
                cur1->next = nullptr;
            }
            else {
                cur2->next = tmp;
                cur2 = cur2->next;
                tmp = tmp->next;
                cur2->next = nullptr;
            }
        }
        //将连个链表合并
        cur1->next = dummy2->next;
        return dummy1->next;
    }
};