CODEWITHSUNDEEP
pythonsortinglinked-listsublist
user2205015
user2205015

Reputation: 85

Sorting a Sublist in a Linked List Python

def sublist(head):
    current=head
    #temp=current #If my list is 3->2->1->4->5->6 it goes into an infinite loop
    while ((current.next is not None) and current.value < current.next.value ):
        temp=current
        current=current.next
    start=current
    while ((current.next is not None) and current.value > current.next.value ):
        current=current.next
    last=current.next
    current.next=None
    first=reverse_linked_list(start)
    temp.next=first

    while first.next is not None:
        first=first.next
    first.next=last

    while head:
        print head.value
        head=head.next
    return head

Working of the code: I give the input to the code as a unordered sublist where sublist within the list is in decending order and the rest of the linked list is in ascending order..

The code works for inputs like 1, 2, 3, 4 ,5, 9, 8, 7, 10 and 1,10,9,8,7,6,5.. i.e an unsorted list in the middle and the end but it doesnt work if the list is unsorted at the beginning for inputs like 3,2,1,4,5,6! Can anyone help me out Please..

Upvotes: 2

Views: 1341

Answers (1)

Isaac Freeman
Isaac Freeman

Reputation: 308

I wasn't able to figure out your code, but I suspect the cause of the infinite loop is that you set temp to current instead of current.value, so you're flipping the cons cells themselves instead of their contents. This is probably creating cyclicly linked lists that you're iterating over infinitely.

However, here is how I would do it (using a basic bubble-sort algorithm):

from functools import total_ordering

@total_ordering
class cons:
    def __init__(self, head, tail=None):
        self.head = head
        self.tail = tail

    @classmethod
    def fromlist(self, l):
        if l == []:
            return None
        return cons(l[0], cons.fromlist(l[1:]))

    def tolist(self):
        if self.tail == None:
            return [self.head]
        else:
            return [self.head] + self.tail.tolist()

    def flip(self):
        if not self.tail == None:
            tmp = self.head
            self.head = self.tail.head
            self.tail.head = tmp

    def __lt__(self, other):
        if other == None:
            return True
        else: 
            return self.head < other.head
    def __eq__(self, other):
        if other == None:
            return False
        else:
            return self.head == other.head

def llsort(head):
    changed = True
    while changed:
        changed = False
        current = head
        while current != None:
            if current > current.tail:
                current.flip()
                changed = True
            current = current.tail

EDIT: The __lt__ and flip are not robust to other uses. In fact I only put the __lt__ and __eq__ there because I was trying to figure out a way to just use one of python's built-in sorting systems but couldn't get that to work. To simplify it a bit:

class cons:
    def __init__(self, head, tail=None):
        self.head = head
        self.tail = tail

    def flip(self):
        if not self.tail == None:
            tmp = self.head
            self.head = self.tail.head
            self.tail.head = tmp


def llsort(head):
    changed = True
    while changed:
        changed = False
        current = head
        while current.tail != None:
            if current.head > current.tail.head:
                current.flip()
                changed = True
            current = current.tail

Upvotes: 1

Related Questions