LeetCode-86-分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

image.png

解题思路：

1. 双指针p和q，分别存储head链表中小于x和大于等于x的节点；
2. 首先开辟两个节点dummp1和dummp2，val=0，p和q分别指向dummp1和dummp2，然后开始遍历head链表，令p指向head.val小于x的节点，而q指向head.val大于等于x的节点；
3. 相当于复制了两份链表dummp1和dummp2，其中dummp1的值均小于dummp2的值；
4. 最后将两个链表拼接起来。

Python3代码：

# 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:
        dummp1 = ListNode(0)
        dummp2 = ListNode(0)
        p = dummp1
        q = dummp2
        while head:
            if head.val < x:
                p.next = head
                p = p.next
            else:
                q.next = head
                q = q.next
            head = head.next
        q.next = None
        p.next = dummp2.next
        return dummp1.next