86.分隔链表
难度：中等
题目：
给你一个链表的头节点 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]
分析
这道题最简单的解题方式，就是我们创建两个小链表和大链表。
然后循环head，当head.val小于x时，追加到小链表，否则添加到大链表
最终将小链表与大链表合并。然后将大链表的链尾置为None。
当然，为了熟悉链表操作，写了一种寻找第一个大链表头的解法。
创建一个空链表，然后循环判断head，当head.val小于x，则直接拼接ret.next = head
当找到第一个大于等于x的val时，设置为刚才我们创建的大链表头，之后进行对比插入。
这个解法是为了进一步熟悉链表操作，自娱自乐...
解题1-双链表合并：
class Solution: def partition(self, head, x): if not head: return head small = ListNode() sm = small large = ListNode() lg = large while head: if head.val < x: sm.next = head sm = sm.next else: lg.next = head lg = lg.next head = head.next lg.next = None sm.next = large.next return small.next
解题2-寻找第一个large链表头：
class Solution: def partition(self, head, x): tmp = ret = ListNode() li = head ins = None while li: if li.val < x: tmp.next = li tmp = tmp.next li = li.next else: ins = li break while li and li.next: if li.next.val < x: tmp.next = li.next tmp = li.next li.next = li.next.next else: li = li.next tmp.next = ins return ret.next
