Merge two sorted linked lists using recursion
Here given code implementation process.
// C Program
// Merge two sorted linked lists using recursion
#include <stdio.h>
#include <stdlib.h> //for malloc function
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// 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->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Returns a new Node of linked list
struct LinkNode *createLinkNode(int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
// Add new Node at end of linked list
void addNode(struct SingleLL *sll, int data)
{
struct LinkNode *node = createLinkNode(data);
if (sll->head == NULL)
{
sll->head = node;
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
// Display linked list element
void display(struct SingleLL *sll)
{
if (sll->head == NULL)
{
printf("\n Empty linked list\n");
return;
}
struct LinkNode *temp = sll->head;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Sorted Merge of two sorted list
struct LinkNode *mergeList(struct LinkNode *l1, struct LinkNode *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 = 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)
{
if (sll2->head == NULL)
{
// When have no element in second linked list
return;
}
else if (sll1->head == NULL)
{
sll1->head = sll2->head;
sll1->tail = sll2->tail;
}
else
{
sll1->head = mergeList(sll1->head, sll2->head);
if (sll2->tail->data > sll1->tail->data)
{
sll1->tail = sll2->tail;
}
else if (sll1->tail->data == sll2->tail->data)
{
// Set new tail node
struct LinkNode *auxiliary = sll1->head;
while (auxiliary->next != NULL)
{
auxiliary = auxiliary->next;
}
sll1->tail = auxiliary;
}
}
sll2->head = NULL;
sll2->tail = NULL;
}
int main()
{
// Create linked list
struct SingleLL *sll1 = newLinkedList();
struct SingleLL *sll2 = newLinkedList();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
addNode(sll1, 1);
addNode(sll1, 7);
addNode(sll1, 8);
addNode(sll1, 15);
addNode(sll1, 19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
addNode(sll2, -2);
addNode(sll2, 5);
addNode(sll2, 6);
addNode(sll2, 12);
addNode(sll2, 16);
addNode(sll2, 18);
addNode(sll2, 19);
addNode(sll2, 31);
printf("\n First Linked List \n");
display(sll1);
printf("\n Second Linked List \n");
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
Second Linked List
-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
*/
// Linked list node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
System.out.print("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
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
public LinkNode mergeList(LinkNode l1, LinkNode 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 = 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)
{
if (other.head == null)
{
// When have no element in second linked list
return;
}
else if (this.head == null)
{
this.head = other.head;
this.tail = other.tail;
}
else
{
this.head = mergeList(this.head, other.head);
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
LinkNode auxiliary = this.head;
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.head = null;
other.tail = null;
}
public static void main(String[] args)
{
// Create linked list
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1);
sll1.addNode(7);
sll1.addNode(8);
sll1.addNode(15);
sll1.addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2);
sll2.addNode(5);
sll2.addNode(6);
sll2.addNode(12);
sll2.addNode(16);
sll2.addNode(18);
sll2.addNode(19);
sll2.addNode(31);
System.out.print("\n First Linked List \n");
sll1.display();
System.out.print("\n Second Linked List \n");
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
Second Linked List
-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
*/
// Linked list node
class LinkNode
{
public:
int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
LinkNode *head;
LinkNode *tail;
SingleLL()
{
this->head = NULL;
this->tail = NULL;
}
//Add new Node at end of linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
this->head = node;
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\n Empty linked list\n";
return;
}
LinkNode *temp = this->head;
//iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Sorted Merge of two sorted list
LinkNode *mergeList(LinkNode *l1, LinkNode *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
void merge(SingleLL *other)
{
// When have no element in second linked list
if (other->head == NULL)
{
return;
}
else if (this->head == NULL)
{
this->head = other->head;
this->tail = other->tail;
}
else
{
this->head = this->mergeList(this->head, other->head);
if (other->tail->data > this->tail->data)
{
this->tail = other->tail;
}
else if (this->tail->data == other->tail->data)
{
// Set new tail node
LinkNode *auxiliary = this->head;
while (auxiliary->next != NULL)
{
auxiliary = auxiliary->next;
}
this->tail = auxiliary;
}
}
other->head = NULL;
other->tail = NULL;
}
};
int main()
{
// Create linked list
SingleLL sll1 = SingleLL();
SingleLL sll2 = SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1);
sll1.addNode(7);
sll1.addNode(8);
sll1.addNode(15);
sll1.addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2);
sll2.addNode(5);
sll2.addNode(6);
sll2.addNode(12);
sll2.addNode(16);
sll2.addNode(18);
sll2.addNode(19);
sll2.addNode(31);
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
Second Linked List
-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
*/
// Linked list node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
Console.Write("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Sorted Merge of two sorted list
public LinkNode mergeList(LinkNode l1, LinkNode 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 = 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
if (other.head == null)
{
return;
}
else if (this.head == null)
{
this.head = other.head;
this.tail = other.tail;
}
else
{
this.head = mergeList(this.head, other.head);
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
LinkNode auxiliary = this.head;
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.head = null;
other.tail = null;
}
public static void Main(String[] args)
{
// Create linked list
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1);
sll1.addNode(7);
sll1.addNode(8);
sll1.addNode(15);
sll1.addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2);
sll2.addNode(5);
sll2.addNode(6);
sll2.addNode(12);
sll2.addNode(16);
sll2.addNode(18);
sll2.addNode(19);
sll2.addNode(31);
Console.Write("\n First Linked List \n");
sll1.display();
Console.Write("\n Second Linked List \n");
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
Second Linked List
-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
*/
// Linked list node
class LinkNode
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
class SingleLL
{
public $head;
public $tail;
function __construct()
{
$this->head = null;
$this->tail = null;
}
//Add new Node at end of linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == null)
{
$this->head = $node;
}
else
{
// Append the node at last position
$this->tail->next = $node;
}
$this->tail = $node;
}
// Display linked list element
public function display()
{
if ($this->head == null)
{
echo "\n Empty linked list\n";
return;
}
$temp = $this->head;
//iterating linked list elements
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
if ($other->head == null)
{
return;
}
else if ($this->head == null)
{
$this->head = $other->head;
$this->tail = $other->tail;
}
else
{
$this->head = $this->mergeList($this->head, $other->head);
if ($other->tail->data > $this->tail->data)
{
$this->tail = $other->tail;
}
else if ($this->tail->data == $other->tail->data)
{
// Set new tail node
$auxiliary = $this->head;
while ($auxiliary->next != null)
{
$auxiliary = $auxiliary->next;
}
$this->tail = $auxiliary;
}
}
$other->head = null;
$other->tail = null;
}
}
function main()
{
// Create linked list
$sll1 = new SingleLL();
$sll2 = new SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
$sll1->addNode(1);
$sll1->addNode(7);
$sll1->addNode(8);
$sll1->addNode(15);
$sll1->addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
$sll2->addNode(-2);
$sll2->addNode(5);
$sll2->addNode(6);
$sll2->addNode(12);
$sll2->addNode(16);
$sll2->addNode(18);
$sll2->addNode(19);
$sll2->addNode(31);
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
Second Linked List
-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
*/
// Linked list node
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
display()
{
if (this.head == null)
{
process.stdout.write("\n Empty linked list\n");
return;
}
var temp = this.head;
//iterating linked list elements
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
if (other.head == null)
{
return;
}
else if (this.head == null)
{
this.head = other.head;
this.tail = other.tail;
}
else
{
this.head = this.mergeList(this.head, other.head);
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
var auxiliary = this.head;
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.head = null;
other.tail = null;
}
}
function main()
{
// Create linked list
var sll1 = new SingleLL();
var sll2 = new SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1);
sll1.addNode(7);
sll1.addNode(8);
sll1.addNode(15);
sll1.addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2);
sll2.addNode(5);
sll2.addNode(6);
sll2.addNode(12);
sll2.addNode(16);
sll2.addNode(18);
sll2.addNode(19);
sll2.addNode(31);
process.stdout.write("\n First Linked List \n");
sll1.display();
process.stdout.write("\n Second Linked List \n");
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
Second Linked List
-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
# Linked list node
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
self.tail = None
# Add new Node at end of linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
self.head = node
else :
# Append the node at last position
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\n Empty linked list")
return
temp = self.head
# iterating linked list elements
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) :
if (other.head == None) :
# When have no element in second linked list
return
elif(self.head == None) :
self.head = other.head
self.tail = other.tail
else :
self.head = self.mergeList(self.head, other.head)
if (other.tail.data > self.tail.data) :
self.tail = other.tail
elif(self.tail.data == other.tail.data) :
# Set new tail node
auxiliary = self.head
while (auxiliary.next != None) :
auxiliary = auxiliary.next
self.tail = auxiliary
other.head = None
other.tail = None
def main() :
# Create linked list
sll1 = SingleLL()
sll2 = SingleLL()
# Sorted linked list 1
# 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1)
sll1.addNode(7)
sll1.addNode(8)
sll1.addNode(15)
sll1.addNode(19)
# Sorted linked list 2
# -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2)
sll2.addNode(5)
sll2.addNode(6)
sll2.addNode(12)
sll2.addNode(16)
sll2.addNode(18)
sll2.addNode(19)
sll2.addNode(31)
print("\n First Linked List ")
sll1.display()
print("\n Second Linked List ")
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
Second Linked List
-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
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
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
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
# Add new Node at end of linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
self.head = node
else
# Append the node at last position
self.tail.next = node
end
self.tail = node
end
# Display linked list element
def display()
if (self.head == nil)
print("\n Empty linked list\n")
return
end
temp = self.head
# iterating linked list elements
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)
if (other.head == nil)
# When have no element in second linked list
return
elsif(self.head == nil)
self.head = other.head
self.tail = other.tail
else
self.head = self.mergeList(self.head, other.head)
if (other.tail.data > self.tail.data)
self.tail = other.tail
elsif(self.tail.data == other.tail.data)
# Set new tail node
auxiliary = self.head
while (auxiliary.next != nil)
auxiliary = auxiliary.next
end
self.tail = auxiliary
end
end
other.head = nil
other.tail = nil
end
end
def main()
# Create linked list
sll1 = SingleLL.new()
sll2 = SingleLL.new()
# Sorted linked list 1
# 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1)
sll1.addNode(7)
sll1.addNode(8)
sll1.addNode(15)
sll1.addNode(19)
# Sorted linked list 2
# -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2)
sll2.addNode(5)
sll2.addNode(6)
sll2.addNode(12)
sll2.addNode(16)
sll2.addNode(18)
sll2.addNode(19)
sll2.addNode(31)
print("\n First Linked List \n")
sll1.display()
print("\n Second Linked List \n")
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
Second Linked List
-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
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data, null);
}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
def this()
{
this(null, null);
}
//Add new Node at end of linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Sorted Merge of two sorted list
def mergeList(l1: LinkNode, l2: LinkNode): LinkNode = {
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
if (other.head == null)
{
return;
}
else if (this.head == null)
{
this.head = other.head;
this.tail = other.tail;
}
else
{
this.head = this.mergeList(this.head, other.head);
if (other.tail.data > this.tail.data)
{
this.tail = other.tail;
}
else if (this.tail.data == other.tail.data)
{
// Set new tail node
var auxiliary: LinkNode = this.head;
while (auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.head = null;
other.tail = null;
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create linked list
var sll1: SingleLL = new SingleLL();
var sll2: SingleLL = new SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1);
sll1.addNode(7);
sll1.addNode(8);
sll1.addNode(15);
sll1.addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2);
sll2.addNode(5);
sll2.addNode(6);
sll2.addNode(12);
sll2.addNode(16);
sll2.addNode(18);
sll2.addNode(19);
sll2.addNode(31);
print("\n First Linked List \n");
sll1.display();
print("\n Second Linked List \n");
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
Second Linked List
-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
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
//Add new Node at end of linked list
func addNode(_ data: Int)
{
let node: LinkNode? = LinkNode(data);
if (self.head == nil)
{
self.head = node;
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
// Display linked list element
func display()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = self.head;
//iterating linked list elements
while (temp != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Sorted Merge of two sorted list
func mergeList(_ l1: LinkNode? , _ l2 : LinkNode? )->LinkNode?
{
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
if (other!.head == nil)
{
return;
}
else if (self.head == nil)
{
self.head = other!.head;
self.tail = other!.tail;
}
else
{
self.head = self.mergeList(self.head, other!.head);
if (other!.tail!.data > self.tail!.data)
{
self.tail = other!.tail;
}
else if (self.tail!.data == other!.tail!.data)
{
// Set new tail node
var auxiliary: LinkNode? = self.head;
while (auxiliary!.next != nil)
{
auxiliary = auxiliary!.next;
}
self.tail = auxiliary;
}
}
other!.head = nil;
other!.tail = nil;
}
}
func main()
{
// Create linked list
let sll1: SingleLL = SingleLL();
let sll2: SingleLL = SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1);
sll1.addNode(7);
sll1.addNode(8);
sll1.addNode(15);
sll1.addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2);
sll2.addNode(5);
sll2.addNode(6);
sll2.addNode(12);
sll2.addNode(16);
sll2.addNode(18);
sll2.addNode(19);
sll2.addNode(31);
print("\n First Linked List ");
sll1.display();
print("\n Second Linked List ");
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
Second Linked List
-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
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
fun addNode(data: Int): Unit
{
var node: LinkNode ? = LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode ? = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Sorted Merge of two sorted list
fun mergeList(l1: LinkNode ? , l2 : LinkNode ? ): LinkNode ?
{
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
if (other.head == null)
{
return;
}
else if (this.head == null)
{
this.head = other.head;
this.tail = other.tail;
}
else
{
this.head = this.mergeList(this.head, other.head);
if (other.tail!!.data > this.tail!!.data)
{
this.tail = other.tail;
}
else if (this.tail!!.data == other.tail!!.data)
{
// Set new tail node
var auxiliary: LinkNode ? = this.head;
while (auxiliary?.next != null)
{
auxiliary = auxiliary.next;
}
this.tail = auxiliary;
}
}
other.head = null;
other.tail = null;
}
}
fun main(args: Array < String > ): Unit
{
// Create linked list
var sll1: SingleLL = SingleLL();
var sll2: SingleLL = SingleLL();
// Sorted linked list 1
// 1 → 7 → 8 → 15 → 19 → NULL
sll1.addNode(1);
sll1.addNode(7);
sll1.addNode(8);
sll1.addNode(15);
sll1.addNode(19);
// Sorted linked list 2
// -2 → 5 → 6 → 12 → 16 → 18 → 19 → 31 → NULL
sll2.addNode(-2);
sll2.addNode(5);
sll2.addNode(6);
sll2.addNode(12);
sll2.addNode(16);
sll2.addNode(18);
sll2.addNode(19);
sll2.addNode(31);
print("\n First Linked List \n");
sll1.display();
print("\n Second Linked List \n");
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
Second Linked List
-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
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.
New Comment