leetcode每日一题2020.1.3

86. 分隔链表

一、题目

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

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

示例：

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

二、题解

模拟法

题解

模拟两个链表，small 表示比 x 小的，large 一个表示比 x 大的，
然后遍历原链表，将值比 x 小的接到 small 后面，否则接到 large 后面，
最后再把 small 链表的尾部和 large 链表的头部连起来。

• 时间复杂度：O(n)，n 是原链表的长度。
• 空间复杂度：O(1)

var partition = function(head, x) {
    let small = new ListNode(0);
    let large = new ListNode(0);
    let smallHead = small, largeHead = large;
    while (head) {
        if (head.val < x) {
            small.next = head;
            small = small.next
        } else {
            large.next = head;
            large = large.next
        }
        head = head.next;
    }
    large.next = null
    small.next = largeHead.next
    return smallHead.next
};