86. 分隔链表

https://leetcode-cn.com/problems/partition-list/

解法一：

新建两条链small和large，遍历原链，遇到比x小的就插入small，否则插入large，最后两条链接起来

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        small, large = ListNode(0), ListNode(0)
        s, l, i = small, large, head
        while i:
            if i.val < x:
                s.next = i
                s = s.next
            else:
                l.next = i
                l = l.next
            i = i.next
        s.next = large.next    #small链接上large链
        l.next = None    #large链末尾置空
        return small.next