Partitioning a linked list around a given value and keeping the original order | Link list Node ; A utility function to create a new node ; Function to make two separate lists and return head after concatenating ; Let us initialize first and last nodes of three linked lists 1 ) Linked list of values smaller than x . 2 ) Linked list of values equal to x . 3 ) Linked list of values greater than x . ; Now iterate original list and connect nodes of appropriate linked lists . ; If current node is equal to x , append it to the list of x values ; If current node is less than X , append it to the list of smaller values ; Append to the list of greater values ; Fix end of greater linked list to None if this list has some nodes ; If smaller list is empty ; If smaller list is not empty and equal list is empty ; If both smaller and equal list are non - empty ; Function to print linked list ; Start with the empty list
class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT new_node = Node ( ) NEW_LINE new_node . data = data NEW_LINE new_node . next = None NEW_LINE return new_node NEW_LINE DEDENT def partition ( head , x ) : NEW_LINE INDENT smallerHead = None NEW_LINE smallerLast = None NEW_LINE greaterLast = None NEW_LINE greaterHead = None NEW_LINE equalHead = None NEW_LINE equalLast = None NEW_LINE while ( head != None ) : NEW_LINE INDENT if ( head . data == x ) : NEW_LINE INDENT if ( equalHead == None ) : NEW_LINE INDENT equalHead = equalLast = head NEW_LINE DEDENT else : NEW_LINE INDENT equalLast . next = head NEW_LINE equalLast = equalLast . next NEW_LINE DEDENT DEDENT elif ( head . data < x ) : NEW_LINE INDENT if ( smallerHead == None ) : NEW_LINE INDENT smallerLast = smallerHead = head NEW_LINE DEDENT else : NEW_LINE INDENT smallerLast . next = head NEW_LINE smallerLast = head NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( greaterHead == None ) : NEW_LINE INDENT greaterLast = greaterHead = head NEW_LINE DEDENT else : NEW_LINE INDENT greaterLast . next = head NEW_LINE greaterLast = head NEW_LINE DEDENT DEDENT head = head . next NEW_LINE DEDENT if ( greaterLast != None ) : NEW_LINE INDENT greaterLast . next = None NEW_LINE DEDENT if ( smallerHead == None ) : NEW_LINE INDENT if ( equalHead == None ) : NEW_LINE INDENT return greaterHead NEW_LINE DEDENT equalLast . next = greaterHead NEW_LINE return equalHead NEW_LINE DEDENT if ( equalHead == None ) : NEW_LINE INDENT smallerLast . next = greaterHead NEW_LINE return smallerHead NEW_LINE DEDENT smallerLast . next = equalHead NEW_LINE equalLast . next = greaterHead NEW_LINE return smallerHead NEW_LINE DEDENT def printList ( head ) : NEW_LINE INDENT temp = head NEW_LINE while ( temp != None ) : NEW_LINE INDENT print ( temp . data , end = " ▁ " ) NEW_LINE temp = temp . next NEW_LINE DEDENT DEDENT head = newNode ( 10 ) NEW_LINE head . next = newNode ( 4 ) NEW_LINE head . next . next = newNode ( 5 ) NEW_LINE head . next . next . next = newNode ( 30 ) NEW_LINE head . next . next . next . next = newNode ( 2 ) NEW_LINE head . next . next . next . next . next = newNode ( 50 ) NEW_LINE x = 3 NEW_LINE head = partition ( head , x ) NEW_LINE printList ( head ) NEW_LINE