Partition

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

We can iterate through the linked list, and add the elements to a new linked list based on their value. Elements less than x will get added to the head of the linked list, and elements greater than x will get added to the tail.

def partition(node, value):
  head = node
  tail = node
  node = node.next

  while(node is not None):
    next_node = node.next

    if(node.value < value):
      node.next = head
      head = node
    else:
      tail.next = node
      tail = node

    node = next_node

  return head

Notice that we are moving pointers, rather than moving data. The computation cost of moving a pointer is much less than the cost of moving data on disk. The algorithm iterates through the linked list once, and therefore the time complexity is \(O(n)\).