86. 分隔链表

题目描述

输入链表头节点 head 和整数 x。链表用数组表示，例如 [1,2,3]。

重新连接节点，把链表分成前后两段：前段是所有值小于 x 的节点，后段是所有值大于或等于 x 的节点。

每一段内部，节点要保持它们在原链表中的先后顺序。返回新链表的头节点。

示例 1

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

解释：小于 3 的 1,2,2 按原顺序在前，其余 4,3,5 按原顺序在后。

示例 2

输入：head = [2,1], x = 2
输出：[1,2]

解释：只有 1 小于 2，排到前面。

数据范围

节点数在 [0, 200] 范围内。
-100 <= Node.val <= 100
-200 <= x <= 200

解题思路

准备两个哑节点 small 和 big，分别作为“小于 x”和“不小于 x”两条链的头，s、b 指向各自的尾。顺序遍历原链表，把每个节点接到对应链的尾部。最后把 big 链尾的 next 置空，再把 small 链尾接到 big.next。只是改接 next，不新建节点。

为什么正确

已处理的节点都已按原顺序接在两条链之一的尾部。

复杂度分析

时间 O(n)，空间 O(1)。

易错点

忘记 b.next = None：原链表里 5 的 next 仍指向最后的 2，会形成环。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        small = ListNode(0)
        big = ListNode(0)
        s, b = small, big
        while head:
            if head.val < x:
                s.next = head
                s = s.next
            else:
                b.next = head
                b = b.next
            head = head.next
        b.next = None
        s.next = big.next
        return small.next

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode s = small, b = big;
        while (head != null) {
            if (head.val < x) {
                s.next = head;
                s = s.next;
            } else {
                b.next = head;
                b = b.next;
            }
            head = head.next;
        }
        b.next = null;
        s.next = big.next;
        return small.next;
    }
}

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode small(0);
        ListNode big(0);
        ListNode *s = &small, *b = &big;
        while (head) {
            if (head->val < x) {
                s->next = head;
                s = s->next;
            } else {
                b->next = head;
                b = b->next;
            }
            head = head->next;
        }
        b->next = nullptr;
        s->next = big.next;
        return small.next;
    }
};

func partition(head *ListNode, x int) *ListNode {
	small := &ListNode{}
	big := &ListNode{}
	s, b := small, big
	for head != nil {
		if head.Val < x {
			s.Next = head
			s = s.Next
		} else {
			b.Next = head
			b = b.Next
		}
		head = head.Next
	}
	b.Next = nil
	s.Next = big.Next
	return small.Next
}

var partition = function(head, x) {
    const small = new ListNode(0);
    const big = new ListNode(0);
    let s = small, b = big;
    while (head) {
        if (head.val < x) {
            s.next = head;
            s = s.next;
        } else {
            b.next = head;
            b = b.next;
        }
        head = head.next;
    }
    b.next = null;
    s.next = big.next;
    return small.next;
};

function partition(head: ListNode | null, x: number): ListNode | null {
    const small = new ListNode(0);
    const big = new ListNode(0);
    let s: ListNode = small, b: ListNode = big;
    while (head) {
        if (head.val < x) {
            s.next = head;
            s = s.next;
        } else {
            b.next = head;
            b = b.next;
        }
        head = head.next;
    }
    b.next = null;
    s.next = big.next;
    return small.next;
}

载入编辑器，自己跑一遍 →

链表专题的其他题目

查看链表全部题目 →