Menu
This is a programming question asked during a written test for an interview. "You have two singly linked lists that are already sorted, you have to merge them and return a the head of the new list without creating any new extra nodes. The returned list should be sorted as well"
The method signature is: Node MergeLists(Node list1, Node list2);
Node class is below:
class Node{ int data; Node next; } I tried many solutions but not creating an extra node screws things. Please help.
Here is the accompanying blog entry http://techieme.in/merging-two-sorted-singly-linked-list/
916
The new list should be made by splicing together the nodes of the first two lists. For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20.
We just need to follow some very simple steps and the steps to join two lists (say 'a' and 'b') are as follows: Traverse over the linked list 'a' until the element next to the node is not NULL. If the element next to the current element is NULL (a->next == NULL) then change the element next to it to 'b' (a->next = b).
function will sort a linked list using the merge sort algorithm. to cut the list from the middle node into two halves. Eventually, we sort each part separately, then we'll merge them to get a single sorted list.
Time Complexity: O(M+N), At every call of recursion, we are adding one node to the output.
Node MergeLists(Node list1, Node list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.data < list2.data) { list1.next = MergeLists(list1.next, list2); return list1; } else { list2.next = MergeLists(list2.next, list1); return list2; } } If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
