Description
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2
Output: [1,2]
Constraints:
The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200
Solution
Use two list node and two tail node for smaller nodes and bigger nodes. Every time add the node to new linked lists.文章来源：https://www.toymoban.com/news/detail-651448.html
Time complexity:
o
(
n
)
o(n)
o(n)
Space complexity:
o
(
1
)
o(1)
o(1)文章来源地址https://www.toymoban.com/news/detail-651448.html
Code
# 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: Optional[ListNode], x: int) -> Optional[ListNode]:
header_smaller, header2 = ListNode(-1), ListNode(-1)
tail1, tail2 = header_smaller, header2
p = head
while p:
if p.val < x:
tail1.next = p
tail1 = tail1.next
else:
tail2.next = p
tail2 = tail2.next
p = p.next
tail1.next = header2.next
tail2.next = None
return header_smaller.next
到了这里，关于leetcode - 86. Partition List的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
