Merge Sort for linked list implementation in python is not working

Question

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.

    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

merge two sorted lists

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 <= 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

split the linked list

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

merge sort

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

main

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()

s = t = LinkedList.Node(None) means s and t both point at the same object. Is that intentional? — Open AI - Opting Out
– Open AI - Opting Out, Commented Jan 19, 2016 at 10:32
yes. this code will keep on adding new nodes to the tail of the linked list using t.next and s.next points to the head of the linked list. — sank
– sank, Commented Jan 19, 2016 at 10:57
my input linked list was 8->3->4->1->7->6 and it returned 8->3->4 — sank
– sank, Commented Jan 19, 2016 at 10:58

Tom Karzes · Accepted Answer · 2016-01-19 12:53:37Z

2

This response applies to an earlier version of the code. See my new response for fixes for the new version of the code.

Ok, it looks like the problem is the way you're returning linked lists from functions. In front_to_back_split, you're assigning to head1 and head2, but those are just parameters to the function. I.e., they're local variables. Assigning to them has no effect on the caller.

A better way to do it is to eliminate head1 and head2 as arguments, and instead just make them ordinary local variables. Then change it to return head1 and head2, like so:

return head1, head2

Then, in merge_sort, you no longer need to allocate a and b. Instead, you can just do:

a, b = front_to_back_split(head)

Similarly, merge_sort should return the new head so the caller can use it. Otherwise the caller has no way to determine what the new list head is.

edited Jan 19, 2016 at 12:53

answered Jan 19, 2016 at 11:30

Tom Karzes

24.3k3 gold badges28 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

sank Over a year ago

made the changes. Now my code prints only the first element. Same logic worked in C.

Tom Karzes Over a year ago

If you can show the new code, I'll find the problem for you.

Tom Karzes Over a year ago

See my new answer, which fixes the new version of the code.

Tom Karzes · Accepted Answer · 2016-01-19 12:52:15Z

1

Ok, I've debugged your updated version and it now works. There are three changes:

At the top of merge_sort there's a bare return. Change it to:
```
return head
```
In merge_sort, change the recursive calls so that they update a and b, as follows:
```
a = merge_sort(a)
b = merge_sort(b)
```
In your main code, after sorting the list, you need a LinkedList with the new head in order to print it, since llist1 will still point to the old head. You can use this:
```
print "Sorted list"
new_head = merge_sort(llist1.head)
new_list = LinkedList()
new_list.head = new_head
new_list.print_list()
```

answered Jan 19, 2016 at 12:52

Tom Karzes

24.3k3 gold badges28 silver badges46 bronze badges

1 Comment

sank Over a year ago

Thanks! I'm a beginner to python and this ans helped me

Collectives™ on Stack Overflow

Merge Sort for linked list implementation in python is not working

merge two sorted lists

split the linked list

merge sort

main

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

merge two sorted lists

split the linked list

merge sort

main

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related