86. 分隔链表

题目链接：86.分隔链表
难度：中等

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

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

提示：
节点数目：[0, 200]

题解

思路：
开始想用快慢指针。slow指向在最后一个小于x的节点，fast正常执行遍历，但发现当fast.val < x时，对fast节点的移动复杂度过高（要处理前面val > x的节点）。后来改变思路，维护两个链表，一个存放val < x的节点，另一个存放val >= x的节点，最后进行拼接。

# 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:
        stx = ListNode()    # smaller than x
        gtx = ListNode()    # greater than x
        p, q = stx, gtx
        while head is not None:
            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 = gtx.next
        return stx.next