LeetCode----Partition List

来源:互联网 时间:1970-01-01

Partition List

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
.

分析:

实现链表的分割,类似于快排中的分割。

我的方法非常简单,遍历链表,建立两个链表,s表示小链表,里面的元素值均小于给定元素x;b表示大链表,里面的元素均大于等于给定元素x。

遍历时,对每个节点进行判断,然后放入对应的s或b的链表,最后再将s和b链表进行连接返回。

代码:

class Solution(object): def partition(self, head, x):""":type head: ListNode:type x: int:rtype: ListNode"""p = headss = s = ListNode(-1) # ss record the start of smaller linkedlist, s record the node in smaller linkedlistsb = b = ListNode(-1) # sb record the start of bigger linkedlist, b record the node in bigger linkedlistwhile p: if p.val >= x:b.next = pp = p.nextb = b.nextb.next = None else:s.next = pp = p.nexts = s.nexts.next = Nones.next = sb.nextreturn ss.next



相关阅读:
Top