Given two linked lists, we have to merge them into a single list by alternatively taking one node from each list.We should do this by re-arranging the links and should not create duplicate nodes while merging.
For example consider the two lists
For example consider the two lists
1 -> 2 -> NULL
3 -> 4 -> NULL
The result should look like the following.
1 -> 3 -> 2 -> 4 -> NULL.
There is no logic required for this problem except arranging the links carefully.
Just take two pointers to the two lists, keep adding the first node followed by the second node by advancing both the pointers at a time.
Come out from the loop when we reach the end of any list.
Lastly copy the remaining nodes from the longer list to the result list.
Below is the C++ implementation of the same. The program can be run through the following test cases.
- Two empty lists
- One empty list and the other non-empty list
- Two lists are of equal length
- Two lists are of unequal length