© 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

I hope you liked the article. ** I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book**, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the **Amazon Giveaway** link to you. **If you like the book please give your review comments on Amazon**. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.