leetcode刷题-86分隔链表

时间:2021-05-06 18:38:43

题目

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。

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

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

思路

建立两个新链表a和b,从头遍历链表,当元素小于x,将元素加入a中,当元素大于x则加入b中,合并ab链表

实现

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
if not head:
return None
sma = sma_p = ListNode(None)
big = big_p = ListNode(None)
while head:
if head.val < x:
sma_p.next = head
sma_p = sma_p.next
else:
big_p.next = head
big_p = big_p.next
head = head.next
big_p.next = None
sma_p.next = big.next
return sma.next