给你一个链表的头节点 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
链表考什么？就是哨兵节点+虚拟节点+链表指针的移动
本题的解题思路：
维护两个链表small、big，分别存储比x小的，比x大的节点
但是有一个问题，维护这两个链表，但是无法获取两个链表的头指针，所以需要给两个链表两个哑节点（dummy node）
# 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: ListNode, x: int) -> ListNode:
if not head:
return head
# 1.维护两个链表small、big，分别存储比x小的，比x大的节点
small, big = ListNode(), ListNode()
# 2.维护这两个链表，但是无法获取两个链表的头指针，所以需要给两个链表两个哑节点（dummy node）
small_dummy_node = small
big_dummy_node = big
cur = head
while cur:
if cur.val < x:
small.next = cur
small = small.next
else:
big.next = cur
big = big.next
cur = cur.next
# 3.small链表的最后一个节点的next指向big哑节点的next，即big链表的头节点
small.next = big_dummy_node.next
# 4.将big链表的最后一个节点的next置为None,
# 这是因为当前节点复用的是原链表的节点，而其next可能指向一个小于x的节点，
# 所以需要切断这个引用
big.next = None
return small_dummy_node.next
node_1 = ListNode(1)
node_4 = ListNode(4)
node_3 = ListNode(3)
node_2 = ListNode(2)
node_5 = ListNode(5)
node_2_bak = ListNode(2)
node_1.next = node_4
node_4.next = node_3
node_3.next = node_2
node_2.next = node_5
node_5.next = node_2_bak
s = Solution()
res = s.partition(node_1, 3)
while res:
print(res.val)
res = res.next