86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list/
Link：https://leetcode.com/problems/partition-list/
模拟法
O(N)
先找到满足条件的插入位置，然后遍历把满足条件的节点按序放入插入位置
# 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:
sentryHead = ListNode(0)
sentryHead.next = head
pre = sentryHead
while pre.next is not None:
if pre.next.val >= x:
break
pre = pre.next
cur = pre
while cur.next is not None:
if cur.next.val >= x:
cur = cur.next
else:
tmp = cur.next
cur.next = cur.next.next
tmp.next = pre.next
pre.next = tmp
pre = pre.next
return sentryHead.next
双指针
O(N)
用两个链表分别保存小于的 + 大于等于的节点，然后把两个链表连接起来
# 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:
small_head = small = ListNode(0)
bigger_head = bigger = ListNode(0)
cur = head
while cur is not None:
if cur.val >= x:
bigger.next = cur
bigger = bigger.next
else:
small.next = cur
small = small.next
cur = cur.next
bigger.next = None
small.next = bigger_head.next
return small_head.next
–End–