题目描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

思路

1.我们可以设置两个亚结点，分别保存小于和大于等于target的链表结点。
2.在遍历链表时，以target为分界值，循环给front和behind赋值。
3.在遍历结束后，现将behind的末尾置空，然后将front和behind拼接即可。

Java代码实现

    public ListNode partition(ListNode head, int x) {
        ListNode p1 = new ListNode(-1);
        ListNode front = p1;
        ListNode p2 = new ListNode(-1);
        ListNode behind = p2;

        while(head != null){
            if(head.val < x){
                p1.next = head;
                p1 = p1.next;
            }else{
                p2.next = head;
                p2 = p2.next;
            }
            head = head.next;
        }

        //将尾部结点的next置为空，否则可能会存在多余结点
        p2.next = null;
        p1.next = behind.next;
        return front.next;
    }