Posted on by Kalkicode
Code Recursion

# Merge two sorted linked lists using recursion

The problem at hand involves merging two sorted linked lists using recursion in a C program. Linked lists are a fundamental data structure in computer science used to store and manage collections of elements. A linked list consists of nodes, where each node contains data and a reference (or link) to the next node in the list. In this program, two sorted linked lists are merged into a single sorted linked list using a recursive approach.

## Problem Statement

You are given two sorted linked lists, and your task is to merge them into a single sorted linked list using recursion. The resulting linked list should maintain the sorted order of elements.

## Idea to Solve

To solve this problem, we will define a recursive function `mergeList` that takes two pointers to nodes of the linked lists as arguments and returns a pointer to the merged list. The function will compare the values of the nodes and recursively merge the smaller node with the rest of the merged list. We will also define a function `merge` that handles the merging of two linked lists by updating the pointers of the original lists.

## Pseudocode

1. Define a `LinkNode` structure to represent a node of the linked list with data and a reference to the next node.
2. Define a `SingleLL` structure to represent the singly linked list with head and tail pointers.
3. Implement a function `newLinkedList` to create a new linked list.
4. Implement a function `createLinkNode` to create a new node with the given data.
5. Implement a function `addNode` to add a new node at the end of the linked list.
6. Implement a function `display` to display the elements of the linked list.
7. Implement a function `mergeList` to merge two sorted linked lists recursively.
• Base cases:
• If one of the lists is empty, return the other list.
• Recursive cases:
• If the value of the first node in the first list is smaller, set the next of the first node to the result of merging the rest of the first list with the second list.
• Otherwise, do the same with the second list and the first list.
• Return the merged list.
8. Implement a function `merge` to handle the request of merging two sorted linked lists.
• Base cases:
• If the second list is empty, return.
• If the first list is empty, set the first list's head and tail pointers to the second list's head and tail pointers.
• Recursive case:
• Merge the first list's head with the result of merging the rest of the first list with the second list.
• Update the tail pointer if necessary.
• Reset the second list's head and tail pointers.
9. In the `main` function:
• Create two new linked lists.
• Add elements to the first and second lists, creating two sorted linked lists.
• Display the original lists.
• Merge the second list into the first list using the `merge` function.
• Display the merged list.

## Code Solution

``````// C Program
// Merge two sorted linked lists using recursion
#include <stdio.h>
#include <stdlib.h> //for malloc function

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->tail = NULL;
}
return sll;
}
// Returns a new Node of linked list
{
// Create dynamic node
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
void addNode(struct SingleLL *sll, int data)
{
{
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
void display(struct SingleLL *sll)
{
{
return;
}
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Sorted Merge of two sorted list
{
if (l1 == NULL)
{
// When l1 empty
return l2;
}
else if (l2 == NULL)
{
// When l2 empty
return l1;
}
if (l1->data < l2->data)
{
l1->next = mergeList(l1->next, l2);
return l1;
}
else
{
l2->next = mergeList(l1, l2->next);
return l2;
}
}
// Handles the request of merging two sorted linked list
void merge(struct SingleLL *sll1, struct SingleLL *sll2)
{
{
// When have no element in second linked list
return;
}
{
sll1->tail = sll2->tail;
}
else
{
if (sll2->tail->data > sll1->tail->data)
{
sll1->tail = sll2->tail;
}
else if (sll1->tail->data == sll2->tail->data)
{
// Set new tail node
while (auxiliary->next != NULL)
{
auxiliary = auxiliary->next;
}
sll1->tail = auxiliary;
}
}
sll2->tail = NULL;
}
int main()
{
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
display(sll1);
display(sll2);
merge(sll1, sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
printf("\n After Merge \n");
display(sll1);
return 0;
}``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````/*
Java Program for
Merge two sorted linked lists using recursion
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
// Sorted Merge of two sorted list
{
if (l1 == null)
{
// When l1 empty
return l2;
}
else if (l2 == null)
{
// When l2 empty
return l1;
}
if (l1.data < l2.data)
{
l1.next = mergeList(l1.next, l2);
return l1;
}
else
{
l2.next = mergeList(l1, l2.next);
return l2;
}
}
// Handles the request of merging two sorted linked list
public void merge(SingleLL other)
{
{
// When have no element in second linked list
return;
}
{
this.tail = other.tail;
}
else
{
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.tail = null;
}
public static void main(String[] args)
{
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display();
sll2.display();
sll1.merge(sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
System.out.print("\n After Merge \n");
sll1.display();
}
}``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program for
Merge two sorted linked lists using recursion
*/

{
public:
int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
cout << "\n Empty linked list\n";
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Sorted Merge of two sorted list
{
if (l1 == NULL)
{
// When l1 empty
return l2;
}
else if (l2 == NULL)
{
// When l2 empty
return l1;
}
if (l1->data < l2->data)
{
l1->next = this->mergeList(l1->next, l2);
return l1;
}
else
{
l2->next = this->mergeList(l1, l2->next);
return l2;
}
}
// Handles the request of merging two sorted linked list
void merge(SingleLL *other)
{
// When have no element in second linked list
{
return;
}
{
this->tail = other->tail;
}
else
{
if (other->tail->data > this->tail->data)
{
this->tail = other->tail;
}
else if (this->tail->data == other->tail->data)
{
// Set new tail node
while (auxiliary->next != NULL)
{
auxiliary = auxiliary->next;
}
this->tail = auxiliary;
}
}
other->tail = NULL;
}
};
int main()
{
SingleLL sll1 = SingleLL();
SingleLL sll2 = SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
cout << "\n First Linked List \n";
sll1.display();
cout << "\n Second Linked List \n";
sll2.display();
sll1.merge(&sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
cout << "\n After Merge \n";
sll1.display();
return 0;
}``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````// Include namespace system
using System;
/*
C# Program for
Merge two sorted linked lists using recursion
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Sorted Merge of two sorted list
{
if (l1 == null)
{
// When l1 empty
return l2;
}
else if (l2 == null)
{
// When l2 empty
return l1;
}
if (l1.data < l2.data)
{
l1.next = mergeList(l1.next, l2);
return l1;
}
else
{
l2.next = mergeList(l1, l2.next);
return l2;
}
}
// Handles the request of merging two sorted linked list
public void merge(SingleLL other)
{
// When have no element in second linked list
{
return;
}
{
this.tail = other.tail;
}
else
{
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.tail = null;
}
public static void Main(String[] args)
{
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display();
sll2.display();
sll1.merge(sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
Console.Write("\n After Merge \n");
sll1.display();
}
}``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````<?php
/*
Php Program for
Merge two sorted linked lists using recursion
*/
{
public \$data;
public \$next;

function __construct(\$data)
{
\$this->data = \$data;
\$this->next = null;
}
}
class SingleLL
{
public \$tail;

function __construct()
{
\$this->tail = null;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
return;
}
while (\$temp != null)
{
echo " ". \$temp->data ." →";
// Visit to next node
\$temp = \$temp->next;
}
echo " NULL\n";
}
// Sorted Merge of two sorted list
public	function mergeList(\$l1, \$l2)
{
if (\$l1 == null)
{
// When l1 empty
return \$l2;
}
else if (\$l2 == null)
{
// When l2 empty
return \$l1;
}
if (\$l1->data < \$l2->data)
{
\$l1->next = \$this->mergeList(\$l1->next, \$l2);
return \$l1;
}
else
{
\$l2->next = \$this->mergeList(\$l1, \$l2->next);
return \$l2;
}
}
// Handles the request of merging two sorted linked list
public	function merge(\$other)
{
// When have no element in second linked list
{
return;
}
{
\$this->tail = \$other->tail;
}
else
{
if (\$other->tail->data > \$this->tail->data)
{
\$this->tail = \$other->tail;
}
else if (\$this->tail->data == \$other->tail->data)
{
// Set new tail node
while (\$auxiliary->next != null)
{
\$auxiliary = \$auxiliary->next;
}
\$this->tail = \$auxiliary;
}
}
\$other->tail = null;
}
}

function main()
{
\$sll1 = new SingleLL();
\$sll2 = new SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
echo "\n First Linked List \n";
\$sll1->display();
echo "\n Second Linked List \n";
\$sll2->display();
\$sll1->merge(\$sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
echo "\n After Merge \n";
\$sll1->display();
}
main();``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````/*
Node Js Program for
Merge two sorted linked lists using recursion
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
// Sorted Merge of two sorted list
mergeList(l1, l2)
{
if (l1 == null)
{
// When l1 empty
return l2;
}
else if (l2 == null)
{
// When l2 empty
return l1;
}
if (l1.data < l2.data)
{
l1.next = this.mergeList(l1.next, l2);
return l1;
}
else
{
l2.next = this.mergeList(l1, l2.next);
return l2;
}
}
// Handles the request of merging two sorted linked list
merge(other)
{
// When have no element in second linked list
{
return;
}
{
this.tail = other.tail;
}
else
{
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.tail = null;
}
}

function main()
{
var sll1 = new SingleLL();
var sll2 = new SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display();
sll2.display();
sll1.merge(sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
process.stdout.write("\n After Merge \n");
sll1.display();
}
main();``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````#   Python 3 Program for
#   Merge two sorted linked lists using recursion

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

class SingleLL :

def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

while (temp != None) :
print("", temp.data ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

#  Sorted Merge of two sorted list
def mergeList(self, l1, l2) :
if (l1 == None) :
#  When l1 empty
return l2

elif(l2 == None) :
#  When l2 empty
return l1

if (l1.data < l2.data) :
l1.next = self.mergeList(l1.next, l2)
return l1
else :
l2.next = self.mergeList(l1, l2.next)
return l2

#  Handles the request of merging two sorted linked list
def merge(self, other) :
#  When have no element in second linked list
return

self.tail = other.tail
else :
if (other.tail.data > self.tail.data) :
self.tail = other.tail

elif(self.tail.data == other.tail.data) :
#  Set new tail node
while (auxiliary.next != None) :
auxiliary = auxiliary.next

self.tail = auxiliary

other.tail = None

def main() :
sll1 = SingleLL()
sll2 = SingleLL()
#   1 → 7 → 8 → 15 → 19 → NULL
#   -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display()
sll2.display()
sll1.merge(sll2)
#  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
print("\n After Merge ")
sll1.display()

if __name__ == "__main__": main()``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````#   Ruby Program for
#   Merge two sorted linked lists using recursion

attr_accessor :data, :next

def initialize(data)
self.data = data
self.next = nil
end

end

class SingleLL
# Define the accessor and reader of class SingleLL

def initialize()
self.tail = nil
end

else
#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

while (temp != nil)
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL\n")
end

#  Sorted Merge of two sorted list
def mergeList(l1, l2)
if (l1 == nil)
#  When l1 empty
return l2
elsif(l2 == nil)
#  When l2 empty
return l1
end

if (l1.data < l2.data)
l1.next = self.mergeList(l1.next, l2)
return l1
else
l2.next = self.mergeList(l1, l2.next)
return l2
end

end

#  Handles the request of merging two sorted linked list
def merge(other)
#  When have no element in second linked list
return
self.tail = other.tail
else
if (other.tail.data > self.tail.data)
self.tail = other.tail
elsif(self.tail.data == other.tail.data)
#  Set new tail node
while (auxiliary.next != nil)
auxiliary = auxiliary.next
end

self.tail = auxiliary
end

end

other.tail = nil
end

end

def main()
sll1 = SingleLL.new()
sll2 = SingleLL.new()
#   1 → 7 → 8 → 15 → 19 → NULL
#   -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display()
sll2.display()
sll1.merge(sll2)
#  -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
print("\n After Merge \n")
sll1.display()
end

main()``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
``````
``````/*
Scala Program for
Merge two sorted linked lists using recursion
*/
{
def this(data: Int)
{
this(data, null);
}
}
{
def this()
{
this(null, null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Sorted Merge of two sorted list
if (l1 == null)
{
// When l1 empty
return l2;
}
else if (l2 == null)
{
// When l2 empty
return l1;
}
if (l1.data < l2.data)
{
l1.next = this.mergeList(l1.next, l2);
return l1;
}
else
{
l2.next = this.mergeList(l1, l2.next);
return l2;
}
}
// Handles the request of merging two sorted linked list
def merge(other: SingleLL): Unit = {
// When have no element in second linked list
{
return;
}
{
this.tail = other.tail;
}
else
{
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.tail = null;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll1: SingleLL = new SingleLL();
var sll2: SingleLL = new SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display();
sll2.display();
sll1.merge(sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
print("\n After Merge \n");
sll1.display();
}
}``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````/*
Swift 4 Program for
Merge two sorted linked lists using recursion
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Sorted Merge of two sorted list
{
if (l1 == nil)
{
// When l1 empty
return l2;
}
else if (l2 == nil)
{
// When l2 empty
return l1;
}
if (l1!.data < l2!.data)
{
l1!.next = self.mergeList(l1!.next, l2);
return l1;
}
else
{
l2!.next = self.mergeList(l1, l2!.next);
return l2;
}
}
// Handles the request of merging two sorted linked list
func merge(_ other: SingleLL? )
{
// When have no element in second linked list
{
return;
}
{
self.tail = other!.tail;
}
else
{
if (other!.tail!.data > self.tail!.data)
{
self.tail = other!.tail;
}
else if (self.tail!.data == other!.tail!.data)
{
// Set new tail node
while (auxiliary!.next  != nil)
{
auxiliary = auxiliary!.next;
}
self.tail = auxiliary;
}
}
other!.tail = nil;
}
}
func main()
{
let sll1: SingleLL = SingleLL();
let sll2: SingleLL = SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display();
sll2.display();
sll1.merge(sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
print("\n After Merge ");
sll1.display();
}
main();``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````
``````/*
Kotlin Program for
Merge two sorted linked lists using recursion
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Sorted Merge of two sorted list
{
if (l1 == null)
{
// When l1 empty
return l2;
}
else if (l2 == null)
{
// When l2 empty
return l1;
}
if (l1.data < l2.data)
{
l1.next = this.mergeList(l1.next, l2);
return l1;
}
else
{
l2.next = this.mergeList(l1, l2.next);
return l2;
}
}
// Handles the request of merging two sorted linked list
fun merge(other: SingleLL): Unit
{
// When have no element in second linked list
{
return;
}
{
this.tail = other.tail;
}
else
{
if (other.tail!!.data > this.tail!!.data)
{
this.tail = other.tail;
}
else if (this.tail!!.data == other.tail!!.data)
{
// Set new tail node
while (auxiliary?.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.tail = null;
}
}
fun main(args: Array < String > ): Unit
{
var sll1: SingleLL = SingleLL();
var sll2: SingleLL = SingleLL();
//  1 → 7 → 8 → 15 → 19 → NULL
//  -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll1.display();
sll2.display();
sll1.merge(sll2);
// -2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL
print("\n After Merge \n");
sll1.display();
}``````

#### Output

`````` First Linked List
1 → 7 → 8 → 15 → 19 → NULL

-2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL

After Merge
-2 → 1 → 5 → 6 → 7 → 8 → 12 → 15 → 16 → 18 → 19 → 19 → 31 → NULL``````

## Time Complexity

The time complexity of merging two sorted linked lists using recursion depends on the number of nodes in the linked lists. In the worst case, where both linked lists have 'n' nodes each, the time complexity is O(n), as each node is processed once. The recursive nature of the algorithm contributes to the overall time complexity of O(n).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post