题解 | #划分链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 如:{1,4,3,2,5,2},3 拆分成2个链表 链表1 < x的 122 链表2 435 到最后不用关心链表1的最后一个节点的next指针
     * 因为最后会让链表1的next指针 指向链表2的头结点, 所以只需要关心链表2的末尾指针 将链表2的最后一个末尾指针指向null
     * 最后将链表1的末尾节点的next指针 指向 链表2的头指针即可 即 122->435
     * 思路就是
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    public ListNode partition (ListNode head, int x) {

        if (head == null) {
            return head;
        }

        //后面追加<x的节点
        ListNode headNode1 = new ListNode(-1);

        //后面追加>=x的节点
        ListNode headNode2 = new ListNode(-2);

        ListNode leftNode = headNode1;
        ListNode rightNode = headNode2;

        ListNode curNode = head;

        while (curNode != null) {

            if (curNode.val < x) {
                leftNode.next = curNode;
                leftNode = curNode;
            }

            if (curNode.val >= x) {
                rightNode.next = curNode;
                rightNode = curNode;
            }

            curNode = curNode.next;
        }

        rightNode.next = null;
        leftNode.next = headNode2.next;

        return headNode1.next;
    }
}