Introduction to the problem statement
Let us look at what the problem says:
Given two singly-linked lists, merge the second list into the first list at alternating positions; if the second link list includes extra nodes, print them as well. The nodes in the second list will be inserted only when positions are available.
Example 1:-
Linked list 1:- 1 --> 2 --> 3 --> null Linked list 2:- 4 --> 5 --> 6 --> null Output after merging:- 1 --> 4 --> 2 --> 5 --> 3 --> 6 --> null |
Explanation:-
Example 2:-
Linked list 1:- 1 --> 2 --> 3 --> null Linked list 2:- 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> null Output after merging:- 1 --> 4 --> 2 --> 5 --> 3 --> 6 --> null 7 --> 8 --> 9 --> null |
Explanation:-
The nodes of the second list should only be inserted when there are positions available in the first list and here the second list has more nodes than the first. To put it simply, the second list can only be inserted if the nodes in it are less than or equal to the nodes in the first list.
As a result, the output is as follows.
Example 3:-
Linked list 1:- empty Linked list 2:- 6 --> 7 --> 8 --> 9 --> null Output after merging:- 6 --> 7 --> 8 --> 9 --> null |
Explanation:-
Since the first list is empty the output will be printed for the second list.
Example 4:-
Linked list 1:- 1 --> 2 --> null Linked list 2:- empty Output after merging:- 1 --> 2 --> null |
Explanation:-
In this case, the second list is empty, thus, the output is printed for the first list.
Example 5:-
Linked list 1:- 1 --> 2 --> 3 --> null Linked list 2:- 4 --> null Output after merging:- 1 --> 4 --> 2 --> 3 --> null |
Explanation:-
Before we move further to the approach let us recall some properties of linked list data structure:
What is a linked list data structure?
- A LinkedList is a collection of elements called nodes that are stored in memory at random.
- A node has two fields: data saved at that specific address and a pointer containing the address of the next node in memory.
- The list's last node contains a pointer to the null.
Source: Vivosoft
In programming, there are many different types of linked lists, but we generally refer to the singly linked list, which is what we've examined in the preceding paragraphs.
This article will help you explore further into the linked list for a better understanding.
Let us now get back to the problem:-
The idea is very simple, if we look closely at the problem examples then it is clear that we need to update the links of the nodes by taking care of the corresponding nodes.
We'll simply run a loop while there are open positions in the first linked list and insert nodes from the second list between the first by altering pointers.
Recommended Topic, Floyds Algorithm
Approach
- Assume Nodes A and B are the beginnings (heads) of two linked lists.
- Take Node result = A ( store the head of the link list one).
- Make Node node1next= A.next and Node node2next = B.next.
- Update the link of node 1.
A.next = B
- Make B.next = node1next. (At this point, B is situated between A and node1next).
- The A pointer should be updated to point to the next node in the first linked list.
A = node1next.
- The B pointer should be updated to point to the next node in the second linked list.
B = node2next.
- Repeat the previous two procedures until one of the items on the list burns out.
- Using the result node, print the list.
- Print the remaining list in B, if any, with B pointing to the top of the list.