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]
提示：
- 链表中节点的数目在范围
[0, 200]内
100 <= Node.val <= 100
200 <= x <= 200
通过次数148,280提交次数234,553
法1
思路
定义四个指针，分别为小于 大于等于的头和尾。
题解
# 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: if head is None or head.next is None: return head l_h,l_t = None, None g_h, g_t =None, None cur = head while cur: nxt = cur.next cur.next = None if cur.val < x: if l_h is None: l_h = cur l_t = cur else: l_t.next = cur l_t = l_t.next else: if g_h is None: g_h = cur g_t = cur else: g_t.next = cur g_t = g_t.next cur = nxt if l_h is None: res = g_h else: l_t.next = g_h res = l_h return res