86. Partition List

新建两个list，小于val去左边，大于去右边，最后拼一拼

无脑新添Node法

public ListNode partition(ListNode head, int x) {
    ListNode l = new ListNode(0),
             r = new ListNode(0);
    ListNode lh = l, rh = r;
    while (head != null) {
        if (head.val < x) {
            l.next = new ListNode(head.val);
            l = l.next;
        } else {
            r.next = new ListNode(head.val);
            r = r.next;
        }
        head = head.next;
    }
    l.next = rh.next;
    return lh.next;
}

不加新node，直接用head，head就像一条蛇游走在l和r之间什么鬼啦。这里有个坑点就是必须加上r.next = null;。比如拿例题head = 1->4->3->2->5->2, x = 3来说，分割完之后lh.next=1->2->2,而rh=4->3->5->2。rh最后这个2和lh最后这个2是一样的node，所以在运行l.next = rh.next;的时候，其实会同时改变l和rh，结果就变成1->2->2->4->3->5->2->4->3->5->2....的无限循环，所以需要删除rh最后这个2。（为什么会有这个2呢是因为在最后一次加node的时候没有新的值了，so这个2没有被覆盖。

public ListNode partition(ListNode head, int x) {
    ListNode l = new ListNode(0), r = new ListNode(0);
    ListNode lh = l, rh = r;
    ListNode node = head;
    while (head != null) {
        if (head.val < x) {
            l.next = head;
            l = l.next;
        } else {
            r.next = head;
            r = r.next;
        }
        head = head.next;
    }
    r.next = null;
    l.next = rh.next;
    return lh.next;
}