题解 | #划分链表#

直观来说我们只需维护两个链表 \textit{small}small 和 \textit{big}big 即可，\textit{small}small 链表按顺序存储所有小于 xx 的节点，\textit{large}large 链表按顺序存储所有大于等于 xx 的节点。遍历完原链表后，我们只要将 \textit{small}small 链表尾节点指向 \textit{large}large 链表的头节点即能完成对链表的分隔。

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return head;
        }
        ListNode smallHead = new ListNode(-1); 
        ListNode bigHead = new ListNode(-1); 
        ListNode  curr = head;
        ListNode smallPtr = smallHead;
        ListNode  bigPtr = bigHead;
        while(curr !=null){
                ListNode temp = curr;
                int value = temp.val;
                if(value<x){
                    ListNode l1 = new ListNode(value);
                    smallPtr.next = l1;
                    smallPtr = l1;

                }else{
                    ListNode l2 = new ListNode(value);
                    bigPtr.next = l2;
                    bigPtr = l2;
                }
                curr = curr.next;
        }
        smallPtr.next =  bigHead.next;
        return smallHead.next;


    }
}