86. Partition List

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */

题目给我们一个链表头 head 以及一个数字 x

要求我们把小于数字 x 的链表元素全部按顺序往前放到所有大于等于数字 x 的链表元素后

所有元素都需要按照原来的顺序排序

最后返回新的链表头

解题思路

我们用两个 dummyHead：

• smallDummy：用来按顺序存放所有小于数字 x 的链表元素
• largeDummy：用来按顺序存放所有大于等于数字 x 的链表元素

我们通过一次循环遍历 head，把小于 x 的链表元素按顺序挂到 smallDummy 后面；其余的按顺序挂到 largeDummy 后面

循环结束后，我们需要把 largeDummy 最后一个指针设置为 null 防止循环链表

然后我们把 smallDummy 最后个元素的 next 指向 largeDummy.next 完成拼接

最后返回 smallDummy.next 即可

Javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    const smallDummy = new ListNode()
    const largeDummy = new ListNode()
    let cur = head
    let small = smallDummy
    let large = largeDummy

    while(cur) {
        if(cur.val < x) {
            small.next = cur
            small = small.next
        } else {
            large.next = cur
            large = large.next
        }
        cur = cur.next
    }

    large.next = null
    small.next = largeDummy.next

    return smallDummy.next
};

复杂度分析

时间

O(n)

空间

O(1)