Merge two linked lists alternatively
Given two linked lists, merge one linked list into another so that each node of second list is inserted into first list at alternate positions. Problem is typical known as merge two linked lists alternatively. When you merge two lists alternatively, first node of one list becomes first node of result, first node of second list becomes second, second node of first list becomes third and so on. Example:
L1 = 3->4->6->7->NULL L2 = 1->8->10->NULL Result = 3->1->4->8->6->10->7->NULL
Constraint for solution is that no additional space should be used while merging two linked lists. This means, we cannot create new nodes, all we can do is to re-arrange nodes of two lists alternatively.
If list are of different lengths, one list will finish before the other, then remaining part of the bigger list should be added at the end of result.
Merge two lists alternatively : Method
In one of our previous posts, we learned how to merge two sorted linked list into one sorted linked list. In that problem, we merged two lists without any additional node being created. We will use same approach. In merge sort method in previous problem, we compare two nodes, and advance pointer of linked list that has smaller node value.
In merging two linked lists alternately, decision to advance list will be very simple : a flag. If flag is true, advance first list pointer and if flag is false, advance second list pointer. Make sure previous node added to resultant node created till now points to newly added node.
Merge two linked lists alternatively implementation
Code is very similar to merging of two sorted linked lists and simple to understand.
Complexity of algorithm to merge two linked list alternatively is O(n+m) where n and m are length of two linked lists.
There is simpler and iterative solution to this problem too. We just need to do some trick with node pointers as shown below.
Code to iterative merge a list into another at alternate positions
Complexity is same O(n+m). Advantage of iterative method over recursive is that no implicit stack memory is used.
Please leave comment if you feel something is wrong or can be improved. Sharing is caring. Please contact us if you want to contribute to website or share an interview experience.