Given two sorted linked lists, how do we merge them without using any extra space. That means we have to re-arrange the links to form a single sorted linked list.
For example let us consider the following two sorted lists as input.
1 -> 3 -> 5 -> 7
2 -> 4 -> 6 -> 8
The output should be
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
The algorithm is simple. We take the smaller node between the two lists in each iteration, and add it to the result list. We do this until we process any of the list to completion. If there is any remaining portion of the other list, we join it with the result list.
Here is the C++ code do this.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| struct Node | |
| { | |
| int data; | |
| Node * next; | |
| }; | |
| void Print(Node * head) | |
| { | |
| while ( head ) | |
| { | |
| cout<< head->data << " "; | |
| head = head->next; | |
| } | |
| cout << endl; | |
| } | |
| Node * Insert(Node * head, int d ) | |
| { | |
| Node * newNode = new Node(); | |
| newNode->data = d; | |
| newNode->next = head; | |
| return newNode; | |
| } | |
| //merge two lists with heads list1 and list2 and returns the pointer to new list | |
| Node* MergeLists(Node *list1, Node* list2) | |
| { | |
| Node * mListHead = NULL;//head of merged list | |
| Node * mListTail = NULL;//tail of merged list | |
| //Trivial cases | |
| if( list1 == NULL ) | |
| return list2; | |
| if( list2B == NULL ) | |
| return list2; | |
| while ( list1 != NULL && list2 != NULL ) | |
| { | |
| Node *temp; | |
| if( list1->data < list2->data ) | |
| { | |
| temp = list1; | |
| list1 = list1->next; | |
| } | |
| else | |
| { | |
| temp = list2; | |
| list2 = list2->next; | |
| } | |
| if( mListHead == NULL ) | |
| { | |
| mListHead = temp; | |
| mListTail = temp; | |
| } | |
| else | |
| { | |
| mListTail->next = temp; | |
| mListTail = temp; | |
| } | |
| } | |
| // If both lists of equal length? | |
| if( list1 == NULL && list2 == NULL ) | |
| mListTail->next = NULL; | |
| else if( list1 == NULL ) //list2 is remaining; join it | |
| mListTail->next = list2; | |
| else | |
| mListTail->next = list1;// list1 is remaining | |
| return mListHead; | |
| } | |
| int main() | |
| { | |
| Node * head = NULL; | |
| head = Insert(head, 9); | |
| head = Insert(head, 7); | |
| head = Insert(head, 5); | |
| head = Insert(head, 3); | |
| head = Insert(head, 1); | |
| Print(head); | |
| Node *head1 = NULL; | |
| head1 = Insert(head1, 10); | |
| head1 = Insert(head1, 8); | |
| head1 = Insert(head1, 6); | |
| head1 = Insert(head1, 4); | |
| head1 = Insert(head1, 2); | |
| Print(head1); | |
| Node *m = MergeLists(head,head1); | |
| Print(m); | |
| return 0; | |
| } |
by