链表：链表分割

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode headNode = new ListNode(9999); // 自定义头结点。添加头结点能方便运算。
        headNode.next = pHead;
        ListNode pre = headNode;
        ListNode p = pHead;
        ListNode q = pHead.next;
        p.next = null;
        while (q != null) { // 尾插法
            if (q.val < x) {
                while (p != null && p.val < x) {
                    pre = p;
                    p = p.next;
                }
                ListNode s = q;
                q = q.next;
                pre.next = s;
                s.next = p;
            } else {
                while (p != null) {
                    pre = p;
                    p = p.next;
                }
                ListNode s = q;
                q = q.next;
                pre.next = s;
                s.next = p;
            }
            pre = headNode;
            p = pre.next;
        }
        return p;
    }
}