Skip to main content

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
Last updated on by Kalkicode




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.

New Comment