Title: Partition List Source: leetcode.com
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.
Python solution
|
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
''' https://leetcode.com/problems/partition-list/ ''' # Definition for singly-linked list. # 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 """ if not (head and head.next): return head low = None high = None temp = head if head.val < x: low = head while temp.next and temp.next.val < x: temp = temp.next else: high = head while temp.next and temp.next.val >= x: temp = temp.next if not temp.next: return head temp_low = None temp_high = None if low: high = temp.next temp_high = high temp_low = temp else: low = temp.next temp_low = low temp_high = temp temp = temp.next.next while temp: #print temp.val if temp.val < x: temp_low.next = temp temp_low = temp else: temp_high.next = temp temp_high = temp temp = temp.next head = low temp_low.next = high temp_high.next = None #print head.val return head |