## 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

### 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:

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:

- Doubly Linked List
- Remove Duplicates from a Linked List
- Merge K Sorted Linked Lists
- Union and Intersection of two Linked Lists
- Merge Linked Lists at alternate positions
- Rearrange a linked list such that all even and odd positioned nodes are together
- Clone a linked list with next and random pointer
- Merge Linked List

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.