Given two linked lists sorted in increasing order. Merge them such a way that the result list is in decreasing order (reverse order).
Examples:
Input: a: 5->10->15->40
b: 2->3->20
Output: res: 40->20->15->10->5->3->2
Input: a: NULL
b: 2->3->20
Output: res: 20->3->2
A Simple Solution is to do following.
1) Reverse first list ‘a’.
2) Reverse second list ‘b’.
3) Merge two reversed lists.
Another Simple Solution is first Merge both lists, then reverse the merged list.
Both of the above solutions require two traversals of linked list.
How to solve without reverse, O(1) auxiliary space (in-place) and only one traversal of both lists?
The idea is to follow merge style process. Initialize result list as empty. Traverse both lists from beginning to end. Compare current nodes of both lists and insert smaller of two at the beginning of the result list.
1) Initialize result list as empty: res = NULL.
2) Let 'a' and 'b' be heads first and second lists respectively.
3) While (a != NULL and b != NULL)
a) Find the smaller of two (Current 'a' and 'b')
b) Insert the smaller value node at the front of result.
c) Move ahead in the list of smaller node.
4) If 'b' becomes NULL before 'a', insert all nodes of 'a'
into result list at the beginning.
5) If 'a' becomes NULL before 'b', insert all nodes of 'a'
into result list at the beginning.
Cpp Programming:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20merge%20two%20sorted%20linked%20list%20such%20that%20merged%20%0A%2F%2F%20list%20is%20in%20reverse%20order%0A%20%0A%2F%2F%20Linked%20List%20Class%0Aclass%20LinkedList%20%7B%0A%20%0A%20%20%20%20Node%20head%3B%20%20%2F%2F%20head%20of%20list%0A%20%20%20%20static%20Node%20a%2C%20b%3B%0A%20%0A%20%20%20%20%2F*%20Node%20Class%20*%2F%0A%20%20%20%20static%20class%20Node%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20void%20printlist(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(node.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20Node%20sortedmerge(Node%20node1%2C%20Node%20node2)%20%7B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20if%20both%20the%20nodes%20are%20null%0A%20%20%20%20%20%20%20%20if%20(node1%20%3D%3D%20null%20%26%26%20node2%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20resultant%20node%0A%20%20%20%20%20%20%20%20Node%20res%20%3D%20null%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20if%20both%20of%20them%20have%20nodes%20present%20traverse%20them%0A%20%20%20%20%20%20%20%20while%20(node1%20!%3D%20null%20%26%26%20node2%20!%3D%20null)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Now%20compare%20both%20nodes%20current%20data%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(node1.data%20%3C%3D%20node2.data)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Node%20temp%20%3D%20node1.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20node1.next%20%3D%20res%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20node1%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20node1%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%20else%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Node%20temp%20%3D%20node2.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20node2.next%20%3D%20res%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20node2%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20node2%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20second%20list%20reached%20end%2C%20but%20first%20list%20has%0A%20%20%20%20%20%20%20%20%2F%2F%20nodes.%20Add%20remaining%20nodes%20of%20first%20list%20at%20the%0A%20%20%20%20%20%20%20%20%2F%2F%20front%20of%20result%20list%0A%20%20%20%20%20%20%20%20while%20(node1%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20Node%20temp%20%3D%20node1.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node1.next%20%3D%20res%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20node1%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node1%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20first%20list%20reached%20end%2C%20but%20second%20list%20has%0A%20%20%20%20%20%20%20%20%2F%2F%20node.%20Add%20remaining%20nodes%20of%20first%20list%20at%20the%0A%20%20%20%20%20%20%20%20%2F%2F%20front%20of%20result%20list%0A%20%20%20%20%20%20%20%20while%20(node2%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20Node%20temp%20%3D%20node2.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node2.next%20%3D%20res%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20node2%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node2%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%20%20%20%20Node%20result%20%3D%20null%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*Let%20us%20create%20two%20sorted%20linked%20lists%20to%20test%0A%20%20%20%20%20%20%20%20%20the%20above%20functions.%20Created%20lists%20shall%20be%0A%20%20%20%20%20%20%20%20%20a%3A%205-%3E10-%3E15%0A%20%20%20%20%20%20%20%20%20b%3A%202-%3E3-%3E20*%2F%0A%20%20%20%20%20%20%20%20list.a%20%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20list.a.next%20%3D%20new%20Node(10)%3B%0A%20%20%20%20%20%20%20%20list.a.next.next%20%3D%20new%20Node(15)%3B%0A%20%0A%20%20%20%20%20%20%20%20list.b%20%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20%20list.b.next%20%3D%20new%20Node(3)%3B%0A%20%20%20%20%20%20%20%20list.b.next.next%20%3D%20new%20Node(20)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22List%20a%20before%20merge%20%3A%22)%3B%0A%20%20%20%20%20%20%20%20list.printlist(a)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22List%20b%20before%20merge%20%3A%22)%3B%0A%20%20%20%20%20%20%20%20list.printlist(b)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20merge%20two%20sorted%20linkedlist%20in%20decreasing%20order%0A%20%20%20%20%20%20%20%20result%20%3D%20list.sortedmerge(a%2C%20b)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Merged%20linked%20list%20%3A%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printlist(result)%3B%0A%20%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]Output:
List A before merge: 5 10 15 List B before merge: 2 3 20 Merged Linked List is: 20 15 10 5 3 2
This solution traverses both lists only once, doesn’t require reverse and works in-place.