欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

86:分割链表

程序员文章站 2022-07-15 13:18:56
...

问题描述

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

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

示例

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

思路

添加一个头结点,以对整个链表有一个共同的处理方式。
如果大于等于x,则跳过。
小于x,看看是不是需要挪动元素。需要挪动用删除结点、插入节点的算法。
不需要挪动则跳过,记得更新insert的值。
86:分割链表

AC代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        last = head
        tmp = ListNode(1)
        tmp.next = head
        head = tmp
        pre = head
        cur = head.next
        insert = head
        while cur:
            if cur.val < x:
                if pre is insert: # 不需要挪动
                    pre = pre.next
                    cur = cur.next
                    insert = insert.next
                else: # 需要挪动
                    pre.next = cur.next
                    cur.next = insert.next
                    insert.next = cur
                    cur = pre.next
                    insert = insert.next
            else:
                pre = pre.next
                cur = cur.next
        return head.next
相关标签: leetcode中等题