• 链表
• 应用
  • 应用1：Leetocde.86
    • 题目
    • 解题思路
    • 代码实现

链表

应用

应用1：Leetocde.86

题目

86. 分隔链表

解题思路

在遍历过程中，将原有的链表分成两部分，使用两个 \(dumy\) 节点 \(large\)、\(small\) ，用于分别记录大于 \(x\) 的节点和小于 \(x\) 的节点，遍历完成之后，将大链表，连接到小链表的结尾即可。

代码实现

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