86 Partition List

题目

Partition List

题解

由于链表插入/删除首尾节点的时间/空间复杂度均为\(O(1)\)，所以我们不需要像分割数组那样分配额外空间。

首先创建左右两个链表，然后遍历输入的链表，把每个节点裁剪出来插入这两个链表，最后把左右链表拼接起来即可。

代码

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        left_list_head = None
        left_list_tail = None
        right_list_head = None
        right_list_tail = None

        current = head
        while current is not None:
            next = current.next
            current.next = None
            if current.val < x:
                if left_list_head is None:
                    left_list_head = current
                    left_list_tail = current
                else:
                    left_list_tail.next = current
                    left_list_tail = current
            else:
                if right_list_head is None:
                    right_list_head = current
                    right_list_tail = current
                else:
                    right_list_tail.next = current
                    right_list_tail = current
            current = next

        if left_list_head is None:
            return right_list_head

        left_list_tail.next = right_list_head
        return left_list_head