Question

create a function to merge and concatenate two linked list l1 =[1,2,4] and l2=[1,3,4]. dont modify l2 (the nodes inserted in l1 should be copies of l2

class Node(object):
def __init__(self, data):
self.data = data
self.next = None
  
class LinkedList(object):
def print_list(self):
cur_node = self.head
while cur_node:
print(cur_node.data)
cur_node = cur_node.next

def __init__(self):
self.head = None;
  
def append(self, data):
new_node = Node(data)

if self.head is None:
self.head = new_node
return

last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node

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
def list_concat(self, llist):
current = self.head
while current.next != None:
current = current.next
current.next = llist
return self.head
llist_1 = LinkedList()
llist_2 = LinkedList()

llist_1.append(1)
llist_1.append(2)
llist_1.append(4)

llist_2.append(1)
llist_2.append(3)
llist_2.append(4)

llist_1.list_concat(llist_2)
llist_1.print_list()

this is my code so far. working for merge sort . But confused in writing concat fumction. How to start?

Code is in python

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Note: The code you provided has indentation messed up, like there is no spaces or tabs before any statements. So I did my best to make it normal. But I’m not sure if I have formatted merge_sorted method correctly. If it is not, ignore it & use your correctly formatted original merge_sorted method. The concat method has been done exactly as needed.

#code

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


class LinkedList(object):
    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

    def __init__(self):
        self.head = None;

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    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

    #required method
    def list_concat(self, llist):
        #taking a reference to the head node of this list
        last=self.head
        #if last is not the last node, advancing last until
        #it becomes the last node on this list
        while last!=None and last.next!=None:
            last=last.next
        #taking a reference to the head node of other list
        current = llist.head
        #looping until current becomes None
        while current!= None:
            #creating a new node with current's data (copy)
            new_node = Node(current.data)
            #if last is None, setting as this node's head
            if last==None:
                self.head=new_node
                #setting this node's head as last, for next iteration
                last=self.head
            else:
                #otherwise, simply appending as the next of last node
                last.next=new_node
                #setting new node as the last node, for next iteration
                last=new_node
            #moving to next node in other list
            current=current.next
        #returning head of this list
        return self.head


llist_1 = LinkedList()
llist_2 = LinkedList()

llist_1.append(1)
llist_1.append(2)
llist_1.append(4)

llist_2.append(1)
llist_2.append(3)
llist_2.append(4)

llist_1.list_concat(llist_2)
llist_1.print_list()

#output

1

2

4

1

3

4