Write a c program to merge two sorted linked lists in sorted order.  For example if one linked list is 1->2->3->null and other is 1->3->5->6->null then the output should be 1->1->2->3->3->5->6->null.

How to approach solution

  • Take two pointers head and current.
  • head pointer will point to first node only.
  • To solve this problem we need to traverse both the linked list.
  • During traversal check the node value of linked list. Suppose if the one linked list is l1 and another is l2.
  • if the node value of l1 is less than equal to the node value of l2, then append l1 to current.
  • else append l2 to current.

C Program to merge two sorted linked lists

#include <stdio.h>
#include <malloc.h>

typedef struct node
{
		int val;
		struct node* next;
} list;

list *l1 = NULL;
list *l2 = NULL;

list* create_node(int val);
void print(list *head);

list* merge(list* l1, list* l2)
{
	if (l1 == NULL) return l2;
	if (l2 == NULL) return l1;
	list *p1 = l1;
	list *p2 = l2;
	list *head = NULL;
	list *cur = NULL;

	while (p1 && p2)
	{
		if (head == NULL)
		{
			if (p1->val <= p2->val)
			{
				head = cur = p1;
				p1 = p1->next;
			}
			else
			{
				head = cur = p2;
				p2 = p2->next;
			}
		}
		else
		{
			if (p1->val <= p2->val)
			{
				cur->next = p1;
				cur = p1;
				p1 = p1->next;
			}
			else
			{
				cur->next = p2;
				cur = p2;
				p2 = p2->next;
			}
		}
	}
	if (p1) cur->next = p1;
	if (p2) cur->next = p2;
	return head;

}

int main()
{
	// create linked list 1->2->3->null
	l1 = create_node(1);
	l1->next = create_node(2);
	l1->next->next = create_node(3);
	l1->next->next->next = NULL;

	// create  1->3->5->6->null
	l2 = create_node(1);
	l2->next = create_node(3);
	l2->next->next = create_node(5);
	l2->next->next->next = create_node(6);
	l2->next->next->next->next = NULL;

	list *res = merge(l1, l2);
	print(res);
	return 0;
}

list* create_node(int val)
{
	list *tmp = (list*) malloc(sizeof(list));
	tmp->next = NULL;
	tmp->val = val;
	return tmp;
}
void print(list* head)
{
	list* current = head;
	while (current)
	{
		printf("%d ", current->val);
		current = current->next;
	}
	printf("\n");
}

Recursive approach

  • We have two linked lists l1 and l2 in sorted order.
  • The  size of l1 could be equal to the size of l2.
  • The size of l1 could be greater than the size of l2.
  • The size of l1 could be less than the size of l2.
  • So the recursive call of merge(l1->next,l2) or merge(l1,l2->next) , would return when smaller list ends. in this case merge the rest of the another list.

Let us see the code ( recursive function to merge two sorted linked lists)

list* merge(list* l1, list* l2)
{
        // if l1 is empty
	if (l1 == NULL) return l2;
        // if l2 is empty
	if (l2 == NULL) return l1;

	if (l1->val <= l2->val)
	{
		l1->next = merge(l1->next, l2);
		return l1;
	}
	else
	{
		l2->next = merge(l1,l2->next);
		return l2;
	}
}

Request:

Send some article to myarticle@wikistack.com to help others.



Related Contents to follow