Partition List

Question

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.

Thoughts

Create两个list,一个存大的一个存小的，所以需要两个dummy node

Solution

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of linked list.
    @param x: an integer
    @return: a ListNode 
    """
    def partition(self, head, x):
        # write your code here
        if not head:
            return None
        dummy1 = ListNode(0)
        left = dummy1
        dummy2 = ListNode(0)
        right = dummy2
        while head:
            if head.val < x:
                dummy1.next = head
                dummy1 = dummy1.next
            else:
                dummy2.next = head
                dummy2 = dummy2.next
            head = head.next
        dummy2.next = None
        dummy1.next = right.next
        return left.next