Interleave two linked lists

© Parineeth M R

Question 10. Interleave two linked lists


Let’s consider two linked lists, L1 having the members A->B->C->D and L2 having the members X->Y->Z. Interleaving the two linked lists will result in the single linked list A->X->B->Y->C->Z->D, wherein the first node of L2 is placed next to the first node of L1, second node of L2 is placed next to second node of L1 and so on. If the sizes of the two linked lists are m and n, then interleaving can be done in O(m+n)

C/C++


/* 
n1: head of the first linked list
n2: head of the second linked list
Return value: head of the result interleaved linked list
*/
struct node* interleave_lists( struct node *n1, struct node *n2)
{
	struct node *result,  *temp1, *temp2;

	if (!n1) {
		return n2; /*If linked list1 is empty, return n2 */
	}
	
	if (!n2) {
		return n1; /*If linked list2 is empty, return n1*/
	}
	
	/*Process the two linked lists*/
	result = n1;
	while (n1 != NULL && n2 != NULL) {
		temp1 = n1->next;
		temp2 = n2->next;

		/*Place node of second linked list next to the node 
		of the first linked list*/
		if (n1->next)
			n2->next = n1->next;
		n1->next = n2;

		n1 = temp1;
		n2 = temp2;
	}
	return result;
}


Java


/* 
n1: head of the first linked list
n2: head of the second linked list
Return value: head of the result interleaved linked list
*/
public static LinkedListNode interleaveLists( LinkedListNode n1, 
					LinkedListNode n2) {

	if (n1 == null) {
		return n2; /*If linked list1 is empty, return n2 */
	}

	if (n2 == null) {
		return n1; /*If linked list2 is empty, return n1*/
	}

	/*Process the two linked lists*/
	LinkedListNode result = n1;
	while (n1 != null && n2 != null) {
		LinkedListNode temp1 = n1.next;
		LinkedListNode temp2 = n2.next;

		/*Place node of second linked list next to the node 
		of the first linked list*/
		if (n1.next != null)
			n2.next = n1.next;
		n1.next = n2;

		n1 = temp1;	
		n2 = temp2;	
	}
	return result;
}



Python


#n1: head of the first linked list
#n2: head of the second linked list
#Return value: head of the result interleaved linked list
@staticmethod
def interleave(n1, n2):
	if (not n1): 
		return n2 #If linked list1 is empty, return n2 

	if (not n2): 
		return n1 #If linked list2 is empty, return n1

	#Process the two linked lists
	result = n1
	while (n1 and n2): 
		temp1 = n1.next
		temp2 = n2.next

		#Place node of second linked list next to the node of 
		#the first linked list
		if (n1.next):
			n2.next = n1.next
		
		n1.next = n2

		n1 = temp1
		n2 = temp2

	return result