描述
Given 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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
分析
就是快排中的parition,但使用链表数据结构,实现有一些不一样。维护两个链表,一个把小于x的值串起来,一个把大于等于x的值串起来,最后把这两个链表拼接起来就可以。时间复杂度O(n)
,空间复杂度O(1)
。
代码
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class ListNode(object): def __init__(self, x): self.val = x self.next = None
class Solution(object): def partition(self, head, x): """ :type head: ListNode :type x: int :rtype: ListNode """ left_dummy = ListNode(-1) right_dummy = ListNode(-1) left_cur = left_dummy right_cur = right_dummy while head: if head.val < x: left_cur.next = head left_cur = head else: right_cur.next = head right_cur = head head = head.next
left_cur.next = right_dummy.next right_cur.next = None return left_dummy.next
|