Sort a linked list, handling pairs as a single item

Question

I am working on this challenge:

Sort a Linked list in increasing order by considering two nodes as a two digit number. (in place sorting)

4 ≤ n ≤ 1000

The length of the linked list is always even.

Example 1:

Input
1→3→4→2→1→2

Output
1→2→1→3→4→2

Explanation:
12 > 13 > 42

Example 2:

Input
1→3→0→3

Output
0→3→1→3

Here is my linked list template implementation; which anyone can start coding:

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

 class Linkedlist():
    def __init__(self):
        self.head = None

    def add(self,x):
        t = Node(x)
        t.next = self.head
        self.head = t

    def display(self):
        p = self.head
        while p != None:
            print(p.data)
            p=p.next

    def sort(self):
        curr = self.head
        # your logic here

m = Linkedlist()
m.add(1)
m.add(3)
m.add(4)
m.add(2)
m.add(1)
m.add(2)
m.display()

Which is the algorithm to sort the pairs in a linked list (in place), and how can I code it?

Answer 1

First of all, your current code will not generate list 1→3→4→2→1→2, but its inverse. This is because your definition of the add method will prepend the given value to the list.

To make add work correctly, it should first find the last node in the list, and append the new node after it. As this is not a very efficient method to add many values to a list, I would suggest to also define add as a Node method, and to allow chaining add calls. That way you can add many values in one chained expression without being inefficient.

Also, as you will need to compare values of pairs, it makes sense to make a method on Node that will return the value of the pair formed by that node and the next in the list.

Finally, for the sort algorithm itself, you could reduce the list to its first pair only (which is then obviously sorted), and treat the rest as a separate list of unsorted nodes. Then extract a pair at a time from the unsorted list, and find the right place to inject it in the main list, so that it remains sorted.

This process represents O(n²) time complexity on average and in the worst case. The best case is O(n), which occurs when the list is originally sorted in reverse order.

Here is how that could look:

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

    # Easy chaining: defining this method on a Node as well
    def add(self, val):
        node = Node(val)
        node.next = self.next
        self.next = node
        return node

    # Define how the value of a pair is calculated
    def pairvalue(self):
        return self.data * 10 + self.next.data

class Linkedlist():
    def __init__(self):
        self.head = None

    def add(self, val):
        # Corrected method: addition should be at the end of the list
        node = Node(val)
        if not self.head:
            self.head = node
        else: # Look for the last node in the list
            curr = self.head
            while curr.next:
                curr = curr.next
            # ...and append the new node after it
            curr.next = node
        return node # Allow for chaining

    def display(self):
        p = self.head
        while p:
            print(p.data,  end= "→")
            p = p.next
        print("NIL")

    def sort(self):
        if not self.head:
            return
        # Reduce list to just its first pair
        # The remainder is a temporary "todo" list
        todo = self.head.next.next
        self.head.next.next = None

        while todo:
            pair = todo # The pair that will be added to the sorted list
            todo = todo.next.next
            val = pair.pairvalue()
            if val < self.head.pairvalue():
                # The pair is a minimum: prepend it
                pair.next.next = self.head
                self.head = pair
            else:
                curr = self.head.next # odd index
                # Find insertion point in sorted list
                while curr.next and curr.next.pairvalue() < val:
                    curr = curr.next.next
                # Perform insertion
                pair.next.next = curr.next
                curr.next = pair

m = Linkedlist()
m.add(1).add(3).add(4).add(2).add(1).add(2)
m.display() # original list
m.sort()
m.display() # final list

The output:

1→3→4→2→1→2→NIL
1→2→1→3→4→2→NIL

Answer 2

First write a function that accepts a linked list of single digit nodes and merges each pair of adjacent single digit nodes into a linked list of half as many nodes, where each node contains a double digit number.

Then sort the resulting linked list using bubble sort, which is O(n^2), or mergesort, which is O(nlogn).

Then, if need be, write a third function that takes apart the double digit nodes and creates a new list of twice as many single digit nodes.

Doing it with two or three functions like this will really simplify the sort.