CareerCup2.4.py

"""
 ============================================================================
 Question        : 2.4 Write code to partition a linked list around a value x, 
                   such that all nodes less than x come before all nodes greater than or equal to x.
 Solution        : I have three linkedlist, one for less, one for equal, one for greater, get all value from original linkedlist, 
                   and save it to correspoding linkedlist, lastly connect these three linkedlist.
 Time Complexity : O(N)
 Space Complexity: O(N)
 Gist Link       : https://gist.github.com/habina/719d2ca521e7695311c9
 ============================================================================
"""

import random

class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

    def __str__(self):
        return chr(self.value)

def print_linkedList(node):
    while node:
        print(node)
        node = node.next
    print

def initialize_linkedList(n):
    if(n < 0):
        print("n has to lager than 0")
        return 0
    random.seed()
    head = Node(random.randint(97, 122), 0)
    n -= 1
    current = head
    while(n > 0):
        temp = Node(random.randint(97, 122), 0)
        current.next = temp
        current = temp
        n -= 1
    return head

def partitionLinkedList(head, x):
    less = Node(0, 0)
    equal = Node(0, 0)
    lager = Node(0, 0)
    currentLess = less
    currentEqual = equal
    currentLager = lager

    #iterator and compare each node
    #save to different linked list
    while head:
        if(head.value < x):
            currentLess.value = head.value
            currentLess.next = Node(0, 0)
            currentLess = currentLess.next
        elif(head.value == x):
            currentEqual.value = head.value
            currentEqual.next = Node(0, 0)
            currentEqual = currentEqual.next
        else:
            currentLager.value = head.value
            currentLager.next = Node(0, 0)
            currentLager = currentLager.next
        head = head.next

    newHead = less
    while less.next.next: # .next.next for avoiding empty node
        less = less.next
    less.next = equal
    while equal.next.next:
        equal = equal.next
    equal.next = lager
    return newHead

a = initialize_linkedList(10)
print("Original Linked List:")
print_linkedList(a)
print()
b = partitionLinkedList(a, a.value)
print("Partitioned Linked List")
print_linkedList(b)