86-分隔链表

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

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

---

示例

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

---

解法

核心思想：x为边界，拆分成两个链表处理，最后在合在一起即可。

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        p = head
        p1 = head1 = ListNode(-1)
        p2 = head2 = ListNode(-1)
        while p != None:
            if p.val < x:
                p1.next = p
                p1 = p1.next
            else:
                p2.next = p
                p2 = p2.next
            p = p.next
        p1.next = head2.next
        p2.next = None # 尾边界
        del head2
        return head1.next

---

相关信息

LeetCode：Discussion | Solution