LeetCode86. 分隔链表

题目链接：LeetCode86

题解

这道题类似荷兰国旗，说一下做法，最简单的方法就是直接将所有的值保存到数组中，然后对数组进行划分，完了以后再重新插回链表中。但是这道题有一个附加要求，要保留每个节点的相对位置，所以这道题应该这么做，首先创建4个节点，分别是ps,pe,qs,qe，然后遍历一遍链表，每次遍历到的当前值cur如果小于指定的值，就将其插到p节点中去，否则就插到q节点中去

代码

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

    ListNode(int val) {
        this.val = val;
    }
}*/
class Solution {
    public ListNode partition(ListNode Head, int x) {
        ListNode ps = null;//p start
        ListNode pe = null;//p end
        ListNode qs = null;//q start
        ListNode qe = null;//q end
        ListNode current = Head;
        while(current != null) {
            ListNode temp = current.next;
            current.next = null;
            if(current.val < x) {
                if(ps == null) {
                    ps = current;
                    pe = current;
                }
                else {
                    pe.next = current;
                    pe = current;
                }
            }
            else{
                 if(qs == null) {
                    qs = current;
                    qe = current;
                }
                else {
                    qe.next = current;
                    qe = current;
                }
            }
            current = temp;
        }
        if(ps == null)
            return qs;
        pe.next = qs;
        return ps;
    }
}