【LeetCode with Python】 86. Partition List


题目类型:Linked List, Two Pointers

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.



class Solution:
    # @param head, a ListNode
    # @param x, an integer
    # @return a ListNode
    def partition(self, head, x):
        if None == head or None == head.next:
            return head
        new_head = ListNode(-1)
        new_head.next = head
        tail = head
        while None != tail.next:
            tail = tail.next
        cur = head
        parent = new_head
        l_pos = new_head

        while tail != parent and None != cur:
            if cur.val >= x:
            parent = parent.next
            cur =  cur.next
            l_pos = l_pos.next
        parent =  parent.next
        if None != cur:
            cur = cur.next
        #l_pos = l_pos.next

        while tail != parent and None != cur:
            if cur.val < x:
                parent.next = cur.next
                cur.next = l_pos.next
                l_pos.next = cur
                l_pos = l_pos.next
                cur = parent.next
                parent = parent.next
                cur =  cur.next
        return new_head.next

results matching ""

    No results matching ""