86.分隔链表

题目描述

题解

双指针

因为题目要求要保留两个分区中每个节点的初始相对位置, 所以就不能采用类似快排的方式在遍历过程中将小于目标值的节点插入到前面.

我们定义两个链表, 一个保存小于目标值的节点, 一个保存大于等于目标值的节点.

然后将两个链表进行拼接

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode beforePart = new ListNode(0);
        ListNode before = beforePart;
        ListNode afterPart = new ListNode(0);
        ListNode after = afterPart;

        while (head != null) {
            if (head.val>=x){
                after.next = head;
                after = after.next;
            }else {
                before.next = head;
                before = before.next;
            }

            head = head.next;
        }

        after.next = null;

        before.next = afterPart.next;

        return beforePart.next;

    }
}