## Algorithm

Problem Name: Data Structures - Merge two sorted linked lists

In this HackerRank in Data Structures - Print in Reverse solutions

his challenge is part of a tutorial track by MyCodeSchool

Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty.

Example

headA refers to 1 -> 3 -> 7 -> NULL

headB refers to 1 -> 2 -> NULL

The new list is 1 -> 1 -> 2 -> 3 -> 7 -> NULL

Function Description

Complete the mergeLists function in the editor below.

mergeLists has the following parameters:

Returns

• SinglyLinkedListNode pointer: a reference to the head of the merged list

Input Format

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

The format for each test case is as follows:

The first line contains an integer n, the length of the first linked list.
The next n lines contain an integer each, the elements of the linked list.
The next line contains an integer m, the length of the second linked list.
The next m lines contain an integer each, the elements of the second linked list.

Constraints

• 1 <= t <= 10
• 1 <= n,m <= 1000
• 1 <= list1[i],list2[i] <= 1000, where list[i] is the i**th element of the list.

Sample Input

``````1
3
1
2
3
2
3
4
``````

Sample Output

``````1 2 3 3 4
``````

Explanation

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

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int data;
};

};

node->data = node_data;
node->next = NULL;

return node;
}

} else {
}

}

while (node) {
fprintf(fptr, "%d", node->data);

node = node->next;

if (node) {
fprintf(fptr, "%s", sep);
}
}
}

while (node) {
node = node->next;

free(temp);
}
}

// Complete the mergeLists function below.

/*
*
*     int data;
* };
*
*/
curr1 = curr1->next;
}
else {
curr2 = curr2->next;
}
curr_new = new_list;
while (curr1 && curr2) {
if (curr1->data  <  curr2->data) {
curr_new->next = curr1;

curr1 = curr1->next;
}
else {
curr_new->next = curr2;

curr2 = curr2->next;
}
curr_new = curr_new->next;
}
if (curr1 != NULL) {
curr_new->next = curr1;
}
if (curr2 != NULL) {
curr_new->next = curr2;
}
return new_list;

}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

char* tests_endptr;
int tests = strtol(tests_str, &tests_endptr, 10);

if (tests_endptr == tests_str || *tests_endptr != '\0') { exit(EXIT_FAILURE); }

for (int tests_itr = 0; tests_itr  <  tests; tests_itr++) {
llist1->tail = NULL;

char* llist1_count_endptr;
int llist1_count = strtol(llist1_count_str, &llist1_count_endptr, 10);

if (llist1_count_endptr == llist1_count_str || *llist1_count_endptr != '\0') { exit(EXIT_FAILURE); }

for (int i = 0; i  <  llist1_count; i++) {
char* llist1_item_endptr;
int llist1_item = strtol(llist1_item_str, &llist1_item_endptr, 10);

if (llist1_item_endptr == llist1_item_str || *llist1_item_endptr != '\0') { exit(EXIT_FAILURE); }

}

llist2->tail = NULL;

char* llist2_count_endptr;
int llist2_count = strtol(llist2_count_str, &llist2_count_endptr, 10);

if (llist2_count_endptr == llist2_count_str || *llist2_count_endptr != '\0') { exit(EXIT_FAILURE); }

for (int i = 0; i  <  llist2_count; i++) {
char* llist2_item_endptr;
int llist2_item = strtol(llist2_item_str, &llist2_item_endptr, 10);

if (llist2_item_endptr == llist2_item_str || *llist2_item_endptr != '\0') { exit(EXIT_FAILURE); }

}

char *sep = " ";

fprintf(fptr, "\n");

}

fclose(fptr);

return 0;
}

size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);

while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);

if (!line) { break; }

data_length += strlen(cursor);

if (data_length  <  alloc_length - 1 || data[data_length - 1] == '\n') { break; }

size_t new_length = alloc_length << 1;
data = realloc(data, new_length);

if (!data) { break; }

alloc_length = new_length;
}

if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}

``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

using namespace std;

public:
int data;

this->data = node_data;
this->next = nullptr;
}
};

public:

this->tail = nullptr;
}

void insert_node(int node_data) {

} else {
this->tail->next = node;
}

this->tail = node;
}
};

while (node) {
fout << node->data;

node = node->next;

if (node) {
fout << sep;
}
}
}

while (node) {
node = node->next;

free(temp);
}
}

if(p1->data  <  p2->data) {
h = p1;
p1 = p1->next;
} else {
h = p2;
p2 = p2->next;
}
p = h;
while(p1!=NULL || p2!=NULL) {
if(!p2 || (p1 && p1->data  <  p2->data)) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
return h;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

int tests;
cin >> tests;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

for (int tests_itr = 0; tests_itr  <  tests; tests_itr++) {

int llist1_count;
cin >> llist1_count;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

for (int i = 0; i  <  llist1_count; i++) {
int llist1_item;
cin >> llist1_item;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

llist1->insert_node(llist1_item);
}

int llist2_count;
cin >> llist2_count;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

for (int i = 0; i  <  llist2_count; i++) {
int llist2_item;
cin >> llist2_item;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

llist2->insert_node(llist2_item);
}

fout << "\n";

}

fout.close();

return 0;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

public int data;

this.data = nodeData;
this.next = null;
}
}

this.tail = null;
}

public void insertNode(int nodeData) {

} else {
this.tail.next = node;
}

this.tail = node;
}
}

public static void printSinglyLinkedList(SinglyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException {
while (node != null) {
bufferedWriter.write(String.valueOf(node.data));

node = node.next;

if (node != null) {
bufferedWriter.write(sep);
}
}
}

}
}
if(t1.data<=t2.data) {
tail = t1;
t1= t1.next;
} else {
tail = t2;
t2 =  t2.next;
}
while(t1!=null && t2!=null) {
if(t1.data < =t2.data) {
tail.next = t1;
tail = t1;
t1 = t1.next;
} else {
tail.next = t2;
tail = t2;
t2 = t2.next;
}

}
if(t1!=null) {
tail.next = t1;
} else {
tail.next = t2;
}
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int tests = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int testsItr = 0; testsItr  <  tests; testsItr++) {

int llist1Count = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int i = 0; i  <  llist1Count; i++) {
int llist1Item = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

llist1.insertNode(llist1Item);
}

int llist2Count = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int i = 0; i  <  llist2Count; i++) {
int llist2Item = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

llist2.insertNode(llist2Item);
}

bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close(>;
}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});

process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*\$/, '')
.split('\n')
.map(str => str.replace(/\s*\$/, ''));

main();
});

return inputString[currentLine++];
}

constructor(nodeData) {
this.data = nodeData;
this.next = null;
}
};

constructor() {
this.tail = null;
}

insertNode(nodeData) {

} else {
this.tail.next = node;
}

this.tail = node;
}
};

while (node != null) {
ws.write(String(node.data));

node = node.next;

if (node != null) {
ws.write(sep);
}
}
}

// Complete the mergeLists function below.

/*
*
*     int data;
* }
*
*/

// Handle empty lists.

while(nodeA || nodeB){
// Handle reaching the end of either list.
if (!nodeA){
break;
}
if (!nodeB){
break;
}

// Select the next lowest node.
if(nodeA.data < nodeB.data){
nodeA = nodeA.next;
}
else {
nodeB = nodeB.next;
}
}

}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

for (let testsItr = 0; testsItr  <  tests; testsItr++) {

for (let i = 0; i  <  llist1Count; i++) {
llist1.insertNode(llist1Item);
}

for (let i = 0; i  <  llist2Count; i++) {
llist2.insertNode(llist2Item);
}

ws.write("\n");
}

ws.end(>;
}
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3

import math
import os
import random
import re
import sys

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

def __init__(self):
self.tail = None

def insert_node(self, node_data):

else:
self.tail.next = node

self.tail = node

while node:
fptr.write(str(node.data))

node = node.next

if node:
fptr.write(sep)

# Complete the mergeLists function below.

#
#
#     int data
#
#

else:

break
break
else:
current = current.next

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

tests = int(input())

for tests_itr in range(tests):
llist1_count = int(input())

for _ in range(llist1_count):
llist1_item = int(input())
llist1.insert_node(llist1_item)

llist2_count = int(input())

for _ in range(llist2_count):
llist2_item = int(input())
llist2.insert_node(llist2_item)