Question

How to sort with bubble sort/merge sort with linked lists, only swapping the data not the nodes (in python)

Answer 1

#Following program demonstrates bubble sort with linked lists with swapping data:

class Node:
    def __init__(self, data):
        self.item = data
        self.ref = None
      
class LinkedList:
    def __init__(self):
        self.start_node = None
  
    def traverse_list(self):
        if self.start_node is None:
            print("List has no element")
            return
        else:
            n = self.start_node
            while n is not None:
                print(n.item , " ")
                n = n.ref

    def insert_at_end(self, data):
        new_node = Node(data)
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;
      
    def bub_sort_datachange(self):
        end = None
        while end != self.start_node:
            p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.item, q.item = q.item, p.item
                p = p.ref
            end = p
          
    def make_new_list(self):
        nums = int(input("How many nodes do you want to create: "))
        if nums == 0:
            return
        for i in range(nums):
            value = int(input("Enter the value for the node:"))
            self.insert_at_end(value)
  
new_linked_list = LinkedList()
new_linked_list.make_new_list()
new_linked_list.bub_sort_datachange()
print("The sorted linked list is:")
new_linked_list.traverse_list()

Sample Run:

Hope this helped. Please do upvote and if there are any queries please ask in comments section.