leetcode 86. 分隔链表（链表的分解）

leetcode 86. 分隔链表（链表的分解）

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

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

解这道题两个关键点：
1. 先分成两个链表，一个链表存放小，另一个存放大的（创建链表用虚拟头结点）
2. 原链表结点给新链表后记得断开与原链表的结点的连接（next = nullptr） !!!

/**
 * 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 *dummyHead1 = new ListNode(-1);    //小于x
        ListNode *dummyHead2 = new ListNode(-1);    //大于或等于x
        ListNode *p1 = dummyHead1;
        ListNode *p2 = dummyHead2;
        ListNode *pcur = head;
        while(pcur) {
            if(pcur->val < x) {
                p1->next = pcur;
                p1 = p1->next;
            }
            else {
                p2->next = pcur;
                p2 = p2->next;
            }
            //如果你不断开原链表中的每个节点的 next 指针
            ListNode* temp = pcur;
            pcur = pcur->next;
            temp->next = nullptr;
        }
        p1->next = dummyHead2->next;
        head = dummyHead1->next;
        delete dummyHead1;
        delete dummyHead2;
        dummyHead1 = nullptr;
        dummyHead2 = nullptr;
        return head;
    }
};

如果你不断开原链表中的每个节点的 next 指针，结果链表中会包含一个环。总的来说，如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，。那其实我们可以养成一个好习惯，但凡遇到这种情况，就把原链表的节点断开，这样就不会出错了。