难度: 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运行时间: 32 ms
内存: 14.9 MB
# 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:
left = ListNode(0)
right = ListNode(0)
p = left
q = right
while head:
tmp = head.next
head.next = None
if head.val < x:
left.next = head
left = left.next
else:
right.next = head
right = right.next
head = tmp
left.next = q.next
return p.next
题解采用了双链表的方式来解决问题。首先创建两个哑节点left和right，分别用来构建小于x和大于等于x的两部分链表。遍历原链表，根据每个节点的值，将其分别链接到left或right链表的尾部。最终，将两个链表连接起来，形成最终的分割链表。这种方法不保留节点在各分区的相对位置，但确保所有小于x的节点都位于大于或等于x的节点前面。
时间复杂度: O(n)
空间复杂度: O(1)
# 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:
left = ListNode(0) # 创建一个新的链表头节点，用于链接所有小于x的节点
right = ListNode(0) # 创建另一个新的链表头节点，用于链接所有大于等于x的节点
p = left # p和q作为移动的指针
q = right
while head: # 遍历原链表
tmp = head.next # 保存当前节点的下一个节点
head.next = None # 断开当前节点，便于单独链接
if head.val < x:
left.next = head # 将当前节点链接到left链表
left = left.next
else:
right.next = head # 将当前节点链接到right链表
right = right.next
head = tmp # 移动到下一个节点
left.next = q.next # 将两个部分的链表链接起来
return p.next # 返回整个分割后的链表的头节点
使用双链表结构可以简化节点的重新链接过程，并减少复杂的指针操作。在原链表上直接进行节点的调整需要多次遍历以确定节点的正确位置，并可能涉及到复杂的节点前驱和后继的处理，这不仅增加了实现的难度，也有可能引入错误。通过创建两个哑节点作为新链表的头部，可以方便地将节点分类并连接，避免了修改原链表的结构，使得操作更为直观和安全。
在连接两个链表之前，通过设置每个节点的next指针为None，确保了每个节点被独立处理并从原链表中断开，这样可以防止未预期的循环引用。连接两个链表时，只涉及将第一个链表的最后一个节点的next指针指向第二个链表的第一个有效节点（right链表的哑节点的next节点），这样的操作简单且不容易出错。通过明确的结束和连接步骤，可以确保链表的正确性和完整性。
代码中已经考虑了链表为空的情况。在while循环开始之前，如果head为None，则循环不会执行，最终函数返回p.next，即为None，符合空链表的预期输出。对于链表中所有元素都小于或等于x的情况，这些元素将全部链接到left或right链表中，而另一个链表将保持为空。连接操作中，如果一个链表为空，则其对应的哑节点的next也将为None，不会影响最终链表的正确性。这样确保了在所有边界情况下，代码都能给出正确的输出。