Alternate arrangement of two linked lists

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

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

	#include <iostream>

	using namespace std;

	struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	};

	ListNode * Add(ListNode *head, int d)
	{
	ListNode *temp = new ListNode(d);
	temp->next = head;
	return temp;
	}

	void Print(ListNode *head)
	{
	if( !head )
	{
	cout << "Empty" << endl;
	return;
	}
	while( head )
	{
	cout << head->val << " ";
	head = head->next;
	}
	cout << endl;
	}

	ListNode * InterleaveLists(ListNode list1, ListNode list2)
	{
	//Base cases
	if( list1 == NULL )
	return list2;
	if( list2 == NULL )
	return list1;

	ListNode resultHead = NULL, resultTail = NULL;
	ListNode first = list1, second = list2;

	while( first != NULL && second != NULL )
	{
	if( resultHead == NULL ) //initial case; executed once
	{
	resultHead = first;
	resultTail = first;
	}
	else
	{
	resultTail->next = first;
	resultTail = first;
	}

	first = first->next;
	resultTail->next = second;
	resultTail = second;
	second = second->next;
	}
	//If any of the two lists is longer than the other, copy remaining elements
	while( first != NULL )
	{
	resultTail->next = first;
	resultTail = first;
	first = first->next;
	}

	while( second != NULL )
	{
	resultTail->next = second;
	resultTail = second;
	second = second->next;
	}

	resultTail->next = NULL;

	return resultHead;
	}

	void Test()
	{
	ListNode *list1 = NULL;
	list1 = Add(list1, 3);
	list1 = Add(list1, 2);
	list1 = Add(list1, 1);

	ListNode *list2 = NULL;
	list2 = Add(list2, 5);
	list2 = Add(list2, 4);

	ListNode *res = InterleaveLists(list1, list2);
	Print(res);
	}

	int main()
	{
	Test();
	return 0;
	}

view raw AlternateTwoLists.cpp hosted with

by GitHub

Leave a Reply Cancel reply