86.分隔链表

86. 分隔链表

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

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

示例:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/partition-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题要求改变链表结构, 使得值小于 x 的元素放在值大于等于 x 的元素的左边。我们使用双指针法，before指针和after指针。

初始化两个指针，before 和 after指针。并创建虚拟头节点
head指针用来遍历当前链表
当 head.val < x 时, 则拼接在before的next
当 head.val > x 时, 则拼接在after 的next
遍历完链表后，我们得到两个链表 before 和 after。
最后将 before 和 after拼接。注意需要清空after.next，防止链表出现环。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public static ListNode partition1(ListNode head, int x) {

        ListNode before = new ListNode(-1);
        ListNode beforeHead = before;
        ListNode after = new ListNode(-1);
        ListNode afterHead = after;

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

            head = head.next;
        }

        after.next = null;
        before.next = afterHead.next;
        return beforeHead.next;
    }

时间复杂度 : O(N) 遍历了链表，其中N是链表长度

空间复杂度 : O(1) 没有申请新的内存空间

Contents

86. 分隔链表

题解：