How can I create a simple function that merges two linked lists in a way that allows me to do the following with something like 'merge(self, other)', also I do not need my merged list to necessarily be sorted - I would like the merge function to simply just add and I've included driver code to give an idea

ls = [2,3,4,5]
ls2 = [42, 17]
ls.merge(ls2) # should change ls to [2,3,4,5,42,17]
ls2.head.data = 24  # should change ls2 to [24,17] and ls to [2,3,4,5,24,17]
    
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def merge_sorted(self, llist):
    
        p = self.head 
        q = llist.head
        s = None
    
        if not p:
            return q
        if not q:
            return p

        if p and q:
            if p.data <= q.data:
                s = p 
                p = s.next
            else:
                s = q
                q = s.next
            new_head = s 
        while p and q:
            if p.data <= q.data:
                s.next = p 
                s = p 
                p = s.next
            else:
                s.next = q
                s = q
                q = s.next
        if not p:
            s.next = q 
        if not q:
            s.next = p 
        return new_head

llist_1 = LinkedList()
llist_2 = LinkedList()

llist_1.append(1)
llist_1.append(5)
llist_1.append(7)
llist_1.append(9)
llist_1.append(10)

llist_2.append(2)
llist_2.append(3)
llist_2.append(4)
llist_2.append(6)
llist_2.append(8)

llist_1.merge_sorted(llist_2)
llist_1.print_list()

CodePudding user response：

def merge(self, other):
    self.tail.next = other.head
    self.tail = other.tail
    self.length  = other.length

CodePudding user response：

To allow for an efficient append and merge implementation you would need to add the tail attribute to your linked list implementation

I would vote against a print_list method, because printing should not be managed by such a class. Instead provide a method that will give a string representation of the list, and let the main program decide whether to print that.

Here is how that could work:

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


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # <-- add this to have an efficient append/merge method

    def append(self, data):
        node = Node(data)
        if not self.head:  # When this list is empty
            self.head = node
        else:
            self.tail.next = node
        self.tail = node

    def merge(self, llist):
        if not self.head:  # When this list is empty
            self.head = llist.head
        else:
            self.tail.next = llist.head
        self.tail == llist.tail

    def __iter__(self):  # To facilitate any need to iterate through the list
        node = self.head
        while node:
            yield node.data
            node = node.next

    def __str__(self):  # Don't make a print method; instead provide a string
        return "->".join(map(str, self))  # This calls self.__iter__()


llist_1 = LinkedList()
llist_2 = LinkedList()

llist_1.append(1)
llist_1.append(5)
llist_1.append(7)
llist_1.append(9)
llist_1.append(10)

llist_2.append(2)
llist_2.append(3)
llist_2.append(4)
llist_2.append(6)
llist_2.append(8)

llist_1.merge(llist_2)
print(llist_1)  # Only call `print` here