Leetcode--86. 分隔链表

题目描述：
给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例：
输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5
运行结果

解题思路
新建两个子链表的头结点：如果节点值小于key，则连在前子链后边，否则连在后子链的后边。最后后子链接在前子链的后边（最后要把后子链的最后置空，不然会产生圈）

注意要求前后节点顺序一致，所以不能采取前后遍历再交换的思路

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode cur=head;
        ListNode pre=new ListNode(0);//前子链的当前节点
        ListNode nex=new ListNode(0);//后子链的当前节点
        head=pre;//head为前子链的头结点
        ListNode lst=nex;//lst为后子链的头结点
        while(cur != null){
            if(cur.val < x){
                pre.next=cur;
                pre=pre.next;//加入前子链
            }else{
                nex.next=cur;
                nex=nex.next;//加入后子链
            }
            cur=cur.next;//遍历原链
        }
        nex.next=null;//后子链结尾置空，防止链表出现圈
        pre.next=lst.next;//前+后连一起
        return head.next;//头结点之后的为所求的链表
    }
}