Examples:<\/strong><\/p>\nInput: a: 5->10->15->40\r\n b: 2->3->20 \r\nOutput: res: 40->20->15->10->5->3->2\r\n\r\nInput: a: NULL\r\n b: 2->3->20 \r\nOutput: res: 20->3->2<\/pre>\nA Simple Solution<\/strong> is to do following.
\n1) Reverse first list \u2018a\u2019.
\n2) Reverse second list \u2018b\u2019.
\n3) Merge two reversed lists.<\/p>\nAnother Simple Solution is first Merge both lists, then reverse the merged list.<\/p>\n
Both of the above solutions require two traversals of linked list.<\/p>\n
How to solve without reverse, O(1) auxiliary space (in-place) and only one traversal of both lists?<\/strong>
\nThe 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.<\/p>\n1) Initialize result list as empty: res = NULL.\r\n2) Let 'a' and 'b' be heads first and second lists respectively.\r\n3) While (a != NULL and b != NULL)\r\n a) Find the smaller of two (Current 'a' and 'b')\r\n b) Insert the smaller value node at the front of result.\r\n c) Move ahead in the list of smaller node. \r\n4) If 'b' becomes NULL before 'a', insert all nodes of 'a' \r\n into result list at the beginning.\r\n5) If 'a' becomes NULL before 'b', insert all nodes of 'a' \r\n into result list at the beginning.<\/pre>\nCpp \u00a0Programming:<\/strong><\/p>\n <\/div>
\/\/ Java program to merge two sorted linked list such that merged \/\/ list is in reverse order \/\/ Linked List Classclass LinkedList { Node head; \/\/ head of list static Node a, b; \/* Node Class *\/ static class Node { int data; Node next; \/\/ Constructor to create a new node Node(int d) { data = d; next = null; } } void printlist(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } Node sortedmerge(Node node1, Node node2) { \/\/ if both the nodes are null if (node1 == null && node2 == null) { return null; } \/\/ resultant node Node res = null; \/\/ if both of them have nodes present traverse them while (node1 != null && node2 != null) { \/\/ Now compare both nodes current data if (node1.data <= node2.data) { Node temp = node1.next; node1.next = res; res = node1; node1 = temp; } else { Node temp = node2.next; node2.next = res; res = node2; node2 = temp; } } \/\/ If second list reached end, but first list has \/\/ nodes. Add remaining nodes of first list at the \/\/ front of result list while (node1 != null) { Node temp = node1.next; node1.next = res; res = node1; node1 = temp; } \/\/ If first list reached end, but second list has \/\/ node. Add remaining nodes of first list at the \/\/ front of result list while (node2 != null) { Node temp = node2.next; node2.next = res; res = node2; node2 = temp; } return res; } public static void main(String[] args) { LinkedList list = new LinkedList(); Node result = null; \/*Let us create two sorted linked lists to test the above functions. Created lists shall be a: 5->10->15 b: 2->3->20*\/ list.a = new Node(5); list.a.next = new Node(10); list.a.next.next = new Node(15); list.b = new Node(2); list.b.next = new Node(3); list.b.next.next = new Node(20); System.out.println("List a before merge :"); list.printlist(a); System.out.println(""); System.out.println("List b before merge :"); list.printlist(b); \/\/ merge two sorted linkedlist in decreasing order result = list.sortedmerge(a, b); System.out.println(""); System.out.println("Merged linked list : "); list.printlist(result); }}<\/code><\/pre> <\/div>\nOutput:<\/strong><\/p>\nList A before merge: \r\n5 10 15 \r\nList B before merge: \r\n2 3 20 \r\nMerged Linked List is: \r\n20 15 10 5 3 2<\/pre>\nThis solution traverses both lists only once, doesn\u2019t require reverse and works in-place.<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Java Programming-Merge two sorted linked lists such that merged list is in reverse order-Linked list
\nGiven two linked lists sorted in increasing<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81476,81750,81477,81749,81748,81474,81479,81483,81475],"class_list":["post-27578","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-singly-linked-list","tag-merge-sort-linked-list-c","tag-merge-two-linked-list-in-c","tag-merge-two-sorted-array","tag-merge-two-sorted-linked-lists-hackerrank","tag-merge-two-sorted-linked-lists-in-java","tag-merge-two-sorted-linked-lists-python","tag-merge-two-sorted-lists-python","tag-merge-two-unsorted-linked-lists-in-c","tag-merging-of-linked-list-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27578","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27578"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27578\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27578"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27578"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27578"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}