跳转至

86. 分隔链表#

问题描述#

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

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

 

示例：


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

解题思路#

将第一个大于等于 \(x\) 结点之后的小于 \(x\) 的结点按顺序放在该结点之前。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        vhead = ListNode()
        vhead.next = head

        p = vhead
        while p.next and p.next.val < x:
            p = p.next

        q = p
        while p.next:
            if p.next.val < x:
                t = p.next
                p.next = p.next.next

                t.next = q.next
                q.next = t
                q = q.next
            else:
                p = p.next
        return vhead.next
返回顶部

在手机上阅读