分隔链表Python解法

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
 

例：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

解析：

使用双链表，一个链表存放大于等于target的值，另一个存放小于target的值，然后首尾相即可。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        p, q = ListNode(), ListNode()  # 初始化两个空节点
        p.next = head  # p指向head
        head = p  # 保留head，第一个链表的头结点，用于存放小于target的值
        head2 = q  # 第二个链表的头结点，用于存放大于等于target的值

        while p.next:  # 循环条件
            if p.next.val < x:
                p = p.next  # 小于，指针直接后移即可
            else:  # 大于等于，跳过，并放入第二个链表里面
                q.next = p.next
                p.next = p.next.next
                q = q.next
                q.next = None
        p.next = head2.next  # 首尾相连

        return head.next  # 返回头结点的next节点即可