Update appNew update is available. Click here to update.
Last Updated: Jun 30, 2023
Medium

Merge One Linked List into Another at Alternate Positions

Author Urwashi Priya
0 upvotes
Linked List

Introduction

In this blog, we will be discussing a linked list data structure problem that has been asked frequently in Interviews.
The problem is to Merge one Linked List into another at alternate positions.

Let us recall what is a linked list.
It is an ordered set of elements, each holding data and a link containing the address to the next element.

To know more about the linked list, refer here. linked-list

illustration image

Problem Statement

We are given N elements in one linked list and M elements in another linked list. We need to merge both the linked list by adding values from the second linked list at the alternate positions in the first linked list. If the second list is larger than the first one, then after the alternate position ends in the first list, just add the remaining elements.

Sample Example

The given 2 lists are:

illustration image

Recommended Topic, Floyds Algorithm

Approach

The best approach is to Merge one Linked List into another at alternate positions.

Declare and define two functions. One is to insert a node at the beginning of a linked list and the other to print a linked list. 

If alternate positions are available in the first linked list, save the next pointers of both the linked list in a variable.

Make current of q as the next of current of p. Update the next pointer of current of p and q.

For further iteration, update the current of p and q.

Update the head pointer of the second list.

 

Time Complexity: The Time complexity is O(N) Since all elements are traversed only once.

Space Complexity: The Space Complexity is O(1) because no extra space is required.

N: No of elements in each list.

 

Till now, I assume you must have got the basic conceptual idea of what has been asked in the given problem statement. So, I recommend you first give it a try.
And solve some related problems on the linked list. say for example:
related problems

Don't be sad if you could not Merge one Linked List into another at alternate positions. This is part of the learning process.
Please have a look at the given algorithm, and then again, you must give it a try.

PseudoCode

Algorithm
___________________________________________________________________
procedure merge(Node *p, Node **q):
___________________________________________________________________
1.   Node *p_curr = p, *q_curr = *q
2.   Node *p_next, *q_next
3.   while (p_curr != NULL && q_curr != NULL):
               p_next = p_curr->next
               q_next = q_curr->next;
               q_curr->next = p_next; 
               p_curr->next = q_curr; 
               p_curr = p_next;
               q_curr = q_next;
4. *q = q_curr; 
end procedure
___________________________________________________________________

Implementation in C++

// C++ program to Merge one Linked List into another at alternate positions
#include <bits/stdc++.h>
using namespace std;

class Node
{
	public:
	int data;
	Node *next;
};

//insertion at the beginning
void push(Node ** head_ref, int new_data)
{
	Node* new_node = new Node();
	new_node->data = new_data;
	new_node->next = (*head_ref);
	(*head_ref) = new_node;
}

// printing a singly linked list 
void printList(Node *head)
{
	Node *temp = head;
	while (temp != NULL)
	{
		cout<<temp->data<<" ";
		temp = temp->next;
	}
	cout<<endl;
}

//merging both linked list according to the given condition. Say p be the first linked list and q be the second linked list.
void merge(Node *p, Node **q)
{
	Node *p_curr = p, *q_curr = *q;
	Node *p_next, *q_next;

	// is alternate position is available in p
	while (p_curr != NULL && q_curr != NULL)
	{
		// Saving the very next pointers
		p_next = p_curr->next;
		q_next = q_curr->next;

		// Making current of q as the next of current of p
		q_curr->next = p_next; 
		p_curr->next = q_curr; 

		// Updating current pointers 
		p_curr = p_next;
		q_curr = q_next;
	}

    // Updating head of second list
	*q = q_curr; 
}

int main()
{
	Node *p = NULL, *q = NULL;
	push(&p, 7);
	push(&p, 5);
	push(&p, 3);
	push(&p, 1);

	push(&q, 9);
	push(&q, 8);
	push(&q, 6);
	push(&q, 4);
	push(&q, 2);

	merge(p, &q);

	printList(p);
	printList(q);

	return 0;
}

Input

1 3 5 7
2 4 6 8 9

Output

1 2 3 4 5 6 7 8 
9

Complexity Analysis

Time Complexity: O(n).

Analysing Time Complexity:

Only a single traversal is required.

Space complexity: O(1). No extra space is required

Frequently Asked Questions

What is a pointer?

Pointer is a variable which is used to store the address of another variable. Different types of pointers are null pointer, dangling pointer, void pointer, etc. the main advantage of using a pointer is that it drastically reduces the time taken to execute a program.

What is the difference between an array and a linked list?

The array consists of a similar data type, which is not necessary in the case of a linked list. The array is stored in a contiguous memory location, whereas a linked list can be stored randomly.

List the difference between a single pointer and a double pointer.

A single pointer is used to store the address of a variable, whereas a double-pointer is basically used to store the address of the first pointer. Single pointer is denoted as *a. Whereas a double-pointer is denoted as **a.

Conclusion

This article taught us how to Merge one Linked List into another at alternate positions. We discussed its implementation using illustrations, pseudocode, and then its proper code.

We hope you could easily take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most linked list problems.
Now, we recommend you practice problem sets based on the linked list to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding.

Previous article
Remove Duplicates from a Sorted Linked List.
Next article
Polynomials Using Linked List and Arrays