题解 | #链表分割#

穷举所有情况，链接节点

人很蠢，看到题解有人用两个链表，一个链接小的数，一个链接大的数，最后拼接起来就是答案。很妙。但是想不出来，直接讨论出所有情况
1.当最开始就是小于的数的时候，也就是cur==head这个时候需要单独出来讨论。因为我们要保证cur和pre是前后的关系，中间不能有节点。如果不分离出来讨论，和cur!=head的情况使用同一份代码(也就是在链表中间遇到比key小的值的情况) 。会出现cur和pre之间多一个节点。最终导致结果直接为空
2. 剩下的就是理清几个指针的指向关系。暴力还是很容易的,想不出简单办法🤡
3. 一般做链表题还是设置一个虚拟头节点，感觉想起来更容易一点，不然讨论的情况会变得复杂

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here

        if(pHead == null) {
            return null;
        }
        ListNode head = new ListNode(0);//虚拟头节点，方便一点
        ListNode resHead = head;//返回节点
        head.next = pHead;
        ListNode cur = head;
        ListNode pre = cur.next;

        while(pre != null) {
            if(pre.val < x){
                if(cur == head){
                    pre = pre.next;
                    cur = cur.next;
                    head = cur;
                }else{
                    ListNode tmp = pre;                
                    cur.next = tmp.next;
                    tmp.next = head.next;
                    head.next = tmp;
                    head = tmp;
                    pre = cur.next;
                }
            }else{
                cur = cur.next;
                pre = pre.next; 
            }

        }
        return resHead.next;
    }
}