难度: Medium
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]
提示：
[0, 200] 内-100 <= Node.val <= 100-200 <= x <= 200运行时间: 44 ms
内存: 15 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
if head is None:
return head
dummy1 = ListNode()
p1 = dummy1
dummy2 = ListNode()
p2 = dummy2
cur = head
while cur:
if cur.val < x:
p1.next = cur
p1 = p1.next
else:
p2.next = cur
p2 = p2.next
cur = cur.next
p2.next = None
p1.next = dummy2.next
return dummy1.next
该题解的思路是将原链表拆分为两个子链表，一个存储所有小于x的节点，一个存储所有大于等于x的节点。创建两个虚拟头节点dummy1和dummy2，分别指向两个子链表。遍历原链表，将每个节点按值的大小关系插入到对应的子链表末尾。最后，将大于等于x的子链表接到小于x的子链表的末尾，并返回小于x子链表的头节点。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
if head is None:
return head
# 创建两个虚拟头节点
dummy1 = ListNode()
p1 = dummy1
dummy2 = ListNode()
p2 = dummy2
cur = head
# 遍历原链表
while cur:
if cur.val < x:
# 插入到小于x的子链表末尾
p1.next = cur
p1 = p1.next
else:
# 插入到大于等于x的子链表末尾
p2.next = cur
p2 = p2.next
cur = cur.next
# 大于等于x的子链表的末尾指向None
p2.next = None
# 将大于等于x的子链表接到小于x的子链表的末尾
p1.next = dummy2.next
return dummy1.next
在题解中，如果链表已经为空，直接返回head是合适的。这是因为处理空链表的结果自然应该是一个空链表，无需进一步处理。直接返回head实际上返回的是null，这恰当地表示了处理后的链表是空的。这种方法清晰地表明了链表为空的情况，并且不需要额外的特殊处理或返回值来区分，因为返回的null已经足够表明链表为空。
在连接两个子链表之前，将大于等于x的子链表的末尾指向None是必要的，以避免引入可能的循环引用。当原链表中的节点被重新分配到两个子链表中时，最后一个大于等于x的节点的next指针可能仍然指向一个小于x的节点，形成一个循环。将此节点的next指针设置为None确保了所有节点都正确地结束，使得子链表成为一个正确的单向序列，从而可以安全地将两个子链表连接起来。
在题解中，通过维护两个指针p1和p2分别指向两个虚拟头节点dummy1和dummy2，然后逐个遍历原链表中的节点，根据节点的值将它们直接链接到相应子链表的末尾来保持节点的相对顺序。这种方法确保了节点插入到子链表中的顺序与它们在原链表中的顺序相同，因此小于x的节点和大于等于x的节点在各自的子链表中保持了原有的相对顺序。
在连接两个子链表之前，因为已经将大于等于x的子链表的末尾节点的next指针设置为None，所以这种操作不会导致原链表中的循环引用。这一步骤是关键的，因为它确保了原链表的末端不会意外地连接回链表的某个中间节点。只要确保这一点，就能安全地将大于等于x的子链表接到小于x的子链表的末尾，而不会引起循环引用的问题。