Merge two sorted linked lists

Input Format

 

The first line contains an integer , denoting the number of test cases.

 

The format for each test case is as follows:

 

The first line contains an integer , denoting the length of the first linked list.

The next  lines contain an integer each, denoting the elements of the linked list.

The next line contains an integer , denoting the length of the second linked list.

The next  lines contain an integer each, denoting the elements of the second linked list.

 

Constraints

 

, where  is the  element of the list.

Output Format

 

For each test case, print in a new line, the linked list after merging them separated by spaces.

 

Sample Input

 

1

3

1

2

3

2

3

4

Sample Output

 

1 2 3 3 4

Explanation

 

The first linked list is: 1 -> 2 -> 3 -> NULL

 

The second linked list is: 3 -> 4 -> NULL

 

Hence, the merged linked list is: 1 -> 2 -> 3 -> 3 -> 4 -> NULL

 

Solution:

 

#!/bin/python3

 

import math

import os

import random

import re

import sys

 

class SinglyLinkedListNode:

    def __init__(self, node_data):

        self.data = node_data

        self.next = None

 

class SinglyLinkedList:

    def __init__(self):

        self.head = None

        self.tail = None

 

    def insert_node(self, node_data):

        node = SinglyLinkedListNode(node_data)

 

        if not self.head:

            self.head = node

        else:

            self.tail.next = node

 

 

        self.tail = node

 

def print_singly_linked_list(node, sep, fptr):

    while node:

        fptr.write(str(node.data))

 

        node = node.next

 

        if node:

            fptr.write(sep)

 

# Complete the mergeLists function below.

 

#

# For your reference:

#

# SinglyLinkedListNode:

#     int data

#     SinglyLinkedListNode next

#

#

def mergeLists(head1, head2):

    if(head1==None and head2==None):

        return 0

    else:

        temp1=head1

        while(temp1.next!=None):

            temp1=temp1.next

        temp2=head2

        temp1.next=temp2

        while(temp2.next!=None):

            temp2=temp2.next

        i=0

        while(i<(llist1_count+llist2_count)):

            temp3=head1

            temp4=temp3.next

            while(temp4!=None):

                if(temp3.data>temp4.data):

 

                    (temp3.data,temp4.data)=(temp4.data,temp3.data)

 

                temp3=temp3.next

                temp4=temp4.next

            i+=1

        return head1

if __name__ == '__main__':

    fptr = open(os.environ['OUTPUT_PATH'], 'w')

tests = int(input())

 

    for tests_itr in range(tests):

        llist1_count = int(input())

 

        llist1 = SinglyLinkedList()

 

        for _ in range(llist1_count):

            llist1_item = int(input())

            llist1.insert_node(llist1_item)

           

        llist2_count = int(input())

 

        llist2 = SinglyLinkedList()

 

        for _ in range(llist2_count):

            llist2_item = int(input())

            llist2.insert_node(llist2_item)

 

        llist3 = mergeLists(llist1.head, llist2.head)

 

        print_singly_linked_list(llist3, ' ', fptr)

        fptr.write('\n')

 

    fptr.close()