86. 分隔链表(Partition List)

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list/

描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

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

题解

双指针法，使用两个指针before和after来追踪两个链表。两个指针可以用于分别创建两个链表，然后将这两个链表连接即可获得所需的链表。

/**
 * 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 beforeHead = new ListNode(0);
        ListNode afterHead = new ListNode(0);
        ListNode before = beforeHead;
        ListNode after = afterHead;
        while (head != null) {
            if (head.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;
    }
}

复杂度分析

• 时间复杂度: ，其中是原链表的长度，我们对该链表进行了遍历；
• 空间复杂度: ，我们没有申请任何新空间。值得注意的是，我们只移动了原有的结点，因此没有使用任何额外空间；