题解 | #划分链表#

思路：把链表分成两个部分，左边是比目标x小的，断链即可，最后再连接起来。

public class Solution {
    public ListNode partition (ListNode head, int x) {
        ListNode left = new ListNode(0);//左链表的尾节点
        ListNode leftHead = left;//左链表的头节点
        ListNode rightHead = new ListNode(0);
        rightHead.next = head;
        ListNode pre = rightHead;//工作指针的前驱
        ListNode cur = pre.next;//工作指针
        while(cur!=null){
            if(cur.val<x){//把小于目标值的节点摘除，尾插到左链表中
                left.next = cur;
                pre.next = cur.next;
                cur.next = null;
                cur = pre.next;
                left = left.next;
            }
            else {
                pre = cur;
                cur = cur.next;
            }
        }
        left.next = rightHead.next;//把链表合起来，然后返回。
        return leftHead.next;
    }
}