Merge sorting a linked list

Question

I've been having trouble using merge sort on a linked list. The issue I've discovered was the problem within my partition method.

Whenever I partition and request the first half, the other half turned out the be the exact same of the previous one. But if I don't request the first half, the second half returns correctly. Here is my code below;

class ListNode:
  def __init__(self, x, next = None):
    self.val = x
    self.next = next

def print_list(root):
  while root:
    print root.val,
    root = root.next
  print ''

def partition(root, is_first_half):
  print_list(root)
  if not root.next:
    return root
  slow_pointer, fast_pointer = root, root.next
  while fast_pointer and fast_pointer.next != None:
    fast_pointer = fast_pointer.next.next
    slow_pointer = slow_pointer.next
  if not is_first_half:
    return slow_pointer
  first_half, first_half_head, first_half_pointer = None, None, root
  while first_half_pointer and first_half_pointer != slow_pointer:
    if not first_half_head:
      first_half = first_half_pointer
      first_half_head = first_half
    else:
      first_half.next = first_half_pointer
      first_half = first_half_pointer
      first_half.next = None
    first_half_pointer = first_half_pointer.next
  return first_half_head


def merge(list1, list2):
    new_list_head, new_list = None, None
    if not list1:
      return list2
    if not list2:
      return list1
    while list1 and list2:
      if list1.val < list2.val:
        if not new_list_head:
          new_list = list1
          new_list_head = new_list
        else:
          new_list.next = list1
          new_list = list1
          new_list.next = None
        list1 = list1.next
      else:
        if not new_list_head:
          new_list = list2
          new_list_head = new_list
        else:
          new_list.next = list2
          new_list = list2
          new_list.next = None
        list2 = list2.next
    if not list1:
      while list2:
        new_list.next = list2
        new_list = list2
        new_list.next = None
        list2 = list2.next
      return new_list_head
    while list1:
      new_list.next = list1
      new_list = list1
      new_list.next = None
      list1 = list1.next
    return new_list_head


def mergesort(root):
  if not root.next:
    return root
  list1 = mergesort(partition(root, True))
  list2 = mergesort(partition(root, False))
  return merge(list1, list2)


if __name__ == '__main__':
  a = ListNode(2, ListNode(4, ListNode(3, ListNode(1, ListNode(7)))))
  print_list(a)
  a = mergesort(a)
  print_list(a)

Answer 1

Do you intend your partitioning to be destructive? That is, should the original list still exist with all its values after you run the partition? You can partition either way.

Destructive partitioning may be a little faster, since it just needs to unlink one node (though finding the right node is O(N)). To get the first half of the list non-destructively you'll need to copy it (creating new nodes for each value). This is also O(N), but probably with larger constant terms due to memory allocation.

Here's a quick destructive partition. It uses different initial values than your code, so we can split directly after the slow_pointer rather than before it (which is more difficult). It also doesn't really make sense to get only one half of a destructive partition at a time, since if you request the first half the second half will become unreachable afterwards, so we return both halves always.

def partition(root):
    fast_pointer = slow_pointer = ListNode(None, root)  # new node "before the root"
    while fast_pointer and fast_pointer.next:
        fast_pointer = fast_pointer.next.next
        slow_pointer = slow_pointer.next
    mid = slow_pointer.next
    slow_pointer.next = None                            # break one link in the list
    return root, mid                                    # return both halves of the list

Here's an alternative version that is non-destructive. The second half of the list is a reference to the same nodes as in the original, but the returned first half is a copy in new nodes

def partition_non_destructive(root):
    root = fast_pointer = slow_pointer = ListNode(None, root)  # root anchors the copy
    while fast_pointer and fast_pointer.next:
        fast_pointer = fast_pointer.next.next
        slow_pointer.next = ListNode(slow_pointer.next.value,  # copy the next node
                                     slow_pointer.next.next)
        slow_pointer = slow_pointer.next  # slow_pointer is always the latest copied node
    mid = slow_pointer.next
    slow_pointer.next = None                           # unlink copied half from the rest
    return root.next, mid                              # return both halves of the list

Both of these functions work correctly for lists of any length, including length one (ListNode("foo")) and zero (None). For odd length lists, the returned first half will always be larger than the second half.

Answer 2

First, in your code for the first half, for the second element you call

first_half = first_half_pointer
first_half.next = None

and then

first_half_pointer = first_half_pointer.next

So first_half_pointer becomes None and the loop finishes, so the first half always has no more than two elements.

Second, and more important, you break the original list connectivity by this line:

first_half.next = None

So after partition(root, True) the second half of the list is lost.

Answer 3

Your merge method seems to have a bug whereby it drops a bunch of elements from the list. Think about what happens in the following line(s) of code:

      new_list.next = None

You are effectively dropping the rest of the list. It seems you will keep the smallest element overall, plus the smallest element of each list for a total of three elements whenever you perform a merge. Try the following main method to see what I mean:

if __name__ == '__main__':
  a = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
  b = ListNode(6, ListNode(7, ListNode(8, ListNode(9, ListNode(10)))))
  print_list(a)
  print_list(b)
  #a = mergesort(a)
  c = merge(a, b)
  print_list(c)
  print_list(a)
  print_list(b)