Merge Sort for linked list implementation in python is not working
<p>Can someone please help me figure out what went wrong with this code? The code is printing the first node in the linked list instead of the sorted linked list.</p>

<pre><code>    class LinkedList(object):  
      def __init__(self):  
      self.head = None  

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

    def push(self, new_data):
       new_node = self.Node(new_data)
       new_node.next = self.head
       self.head = new_node

    def print_list(self):
       temp = self.head
       while(temp):
          print temp.data
          temp = temp.next
</code></pre>

<h1>merge two sorted lists</h1>

<pre><code>def merge_lists(head1, head2):

   if(head1 is None):
      return head2
   if(head2 is None):
      return head1

   s = t= LinkedList.Node(None)

   while(head1 and head2):
     if(head1.data &lt;= head2.data):
        c= head1
        head1 = head1.next
     else:
        c= head2
        head2 = head2.next

     t.next = c 
     t = t.next
  t.next = head1 or head2
  return s.next
</code></pre>

<h1>split the linked list</h1>

<pre><code>def front_back_split(head):
   if(head is None or head.next is None):
      head1 = head
      head2 = None
   else:
      slow = head
      fast = head.next
      while(fast != None):
         fast = fast.next
         if(fast!=None):
            slow = slow.next
            fast = fast.next

   head1 = head
   head2 = slow.next
   slow.next = None

   return head1, head2
</code></pre>

<h1>merge sort</h1>

<pre><code>def merge_sort(head):
   if(head is None or head.next is None):
      return 

   a,b = front_back_split(head)


   merge_sort(a)
   merge_sort(b)

   new_head = merge_lists(a,b)

   return new_head
</code></pre>

<h2>main</h2>

<pre><code>if __name__=='__main__':
   llist1 = LinkedList()
   llist1.push(6)
   llist1.push(7)
   llist1.push(1)
   llist1.push(4)
   llist1.push(3)
   llist1.push(8)



   print "Sorted list"
   new_head = merge_sort(llist1.head)
   llist1.print_list()
</code></pre>