【Leetcode刷题Python】86.分隔链表

1 题目

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。

2 解析

初始化两个空节点，dummy1和dummy2，分别存储小于x的元素和大于等于x的元素。
遍历链表，将所有小于x的元素链接到dummy1上，将大于等于x的链接到dummy2上，最后给dummy2添加一个null尾巴。再将两条链表dummy1和dummy2合并，形成一条新的链表。

3 Python 代码实现

    def partition(self, head: ListNode, x: int) -> ListNode:
        dummy1,dummy2 = ListNode(),ListNode()
        curr1,curr2,curr = dummy1,dummy2,head
        while curr:
            if curr.val <x:
                curr1.next = curr
                curr1 = curr1.next
            else :
                curr2.next = curr
                curr2 = curr2.next
            curr = curr.next
        curr1.next,curr2.next = dummy2.next,None
        # 注意返回是头节点的后一个元素开始的链表
        return dummy1.next