86. 分隔链表

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的 初始相对位置(相对位置就是说 1在2前面那最终1就还得在2前面)

示例
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

思路 : 分隔法，先把链表分隔为两个新的链表 lDummyHead 和 rDummyHead，最终再把两个两边拼接就得到想要的结果

class Solution {
    public ListNode partition(ListNode head, int x) {
        
        if(head==null) return head;
        
        //1.定义两个分隔链表
        //左链表
        ListNode lDummyHead = new ListNode(0);
        ListNode lTail = lDummyHead;
        //右链表
        ListNode rDummyHead = new ListNode(0);
        ListNode rTail = rDummyHead;
        
        //2. 循环组装两个新链表
        while(head != null) {
            // < x 
            if(head.val < x){
               lTail.next = head;
               lTail = head;
            }else {//>=x
               rTail.next = head;
               rTail = head;
            }
           head = head.next; 
        }

        /**  
         3. 清空rTail.next
         这句代码必不可少:rTail.next = null
         因为可能出现这样的情况：
         原链表倒数第N个结点A的值是 >=x 的，A后面所有结点的值都是 <x 的，然后rTail.next最终其实就是
         A.next, 这时就形成了环形链表 这不是我们需要的结果，所以要清空rTail.next
         */
        rTail.next = null;

        //4.拼接两个链表
        lTail.next = rDummyHead.next;

        return lDummyHead.next;

    }
}