{"id":27369,"date":"2018-02-01T21:28:50","date_gmt":"2018-02-01T15:58:50","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27369"},"modified":"2018-02-01T21:28:50","modified_gmt":"2018-02-01T15:58:50","slug":"c-algorithm-merge-two-sorted-linked-lists","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-merge-two-sorted-linked-lists\/","title":{"rendered":"Cpp Algorithm &#8211; Merge two sorted linked lists"},"content":{"rendered":"<p>Write a SortedMerge() function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. SortedMerge() should return the new list.<span id=\"more-3622\"><\/span> The new list should be made by splicing<br \/>\ntogether the nodes of the first two lists.<\/p>\n<p>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.<\/p>\n<p>There are many cases to deal with: either \u2018a\u2019 or \u2018b\u2019 may be empty, during processing either \u2018a\u2019 or \u2018b\u2019 may run out first, and finally there\u2019s the problem of starting the result list empty, and building it up while going through \u2018a\u2019 and \u2018b\u2019.<\/p>\n<p><strong>Method 1 (Using Dummy Nodes)<\/strong><br \/>\nThe strategy here uses a temporary dummy node as the start of the result list. The pointer Tail always points to the last node in the result list, so appending new nodes is easy.<br \/>\nThe dummy node gives tail something to point to initially when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either \u2018a\u2019 or \u2018b\u2019, and adding it to tail. When<br \/>\nwe are done, the result is in dummy.next.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F*%20C%2FC%2B%2B%20program%20to%20merge%20two%20sorted%20linked%20lists%20*%2F%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%23include%3Cassert.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20pull%20off%20the%20front%20node%20of%20the%20source%20and%20put%20it%20in%20dest%20*%2F%0Avoid%20MoveNode(struct%20node**%20destRef%2C%20struct%20node**%20sourceRef)%3B%0A%20%0A%2F*%20Takes%20two%20lists%20sorted%20in%20increasing%20order%2C%20and%20splices%0A%20%20%20their%20nodes%20together%20to%20make%20one%20big%20sorted%20list%20which%0A%20%20%20is%20returned.%20%20*%2F%0Astruct%20node*%20SortedMerge(struct%20node*%20a%2C%20struct%20node*%20b)%0A%7B%0A%20%20%20%20%2F*%20a%20dummy%20first%20node%20to%20hang%20the%20result%20on%20*%2F%0A%20%20%20%20struct%20node%20dummy%3B%0A%20%0A%20%20%20%20%2F*%20tail%20points%20to%20the%20last%20result%20node%20%20*%2F%0A%20%20%20%20struct%20node*%20tail%20%3D%20%26dummy%3B%0A%20%0A%20%20%20%20%2F*%20so%20tail-%3Enext%20is%20the%20place%20to%20add%20new%20nodes%0A%20%20%20%20%20%20to%20the%20result.%20*%2F%0A%20%20%20%20dummy.next%20%3D%20NULL%3B%0A%20%20%20%20while%20(1)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(a%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20if%20either%20list%20runs%20out%2C%20use%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20other%20list%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20tail-%3Enext%20%3D%20b%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%20if%20(b%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20tail-%3Enext%20%3D%20a%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20if%20(a-%3Edata%20%3C%3D%20b-%3Edata)%0A%20%20%20%20%20%20%20%20%20%20%20%20MoveNode(%26(tail-%3Enext)%2C%20%26a)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20MoveNode(%26(tail-%3Enext)%2C%20%26b)%3B%0A%20%0A%20%20%20%20%20%20%20%20tail%20%3D%20tail-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20return(dummy.next)%3B%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20MoveNode()%20function%20takes%20the%20node%20from%20the%20front%20of%20the%0A%20%20%20source%2C%20and%20move%20it%20to%20the%20front%20of%20the%20dest.%0A%20%20%20It%20is%20an%20error%20to%20call%20this%20with%20the%20source%20list%20empty.%0A%20%0A%20%20%20Before%20calling%20MoveNode()%3A%0A%20%20%20source%20%3D%3D%20%7B1%2C%202%2C%203%7D%0A%20%20%20dest%20%3D%3D%20%7B1%2C%202%2C%203%7D%0A%20%0A%20%20%20Affter%20calling%20MoveNode()%3A%0A%20%20%20source%20%3D%3D%20%7B2%2C%203%7D%0A%20%20%20dest%20%3D%3D%20%7B1%2C%201%2C%202%2C%203%7D%20*%2F%0Avoid%20MoveNode(struct%20node**%20destRef%2C%20struct%20node**%20sourceRef)%0A%7B%0A%20%20%20%20%2F*%20the%20front%20source%20node%20%20*%2F%0A%20%20%20%20struct%20node*%20newNode%20%3D%20*sourceRef%3B%0A%20%20%20%20assert(newNode%20!%3D%20NULL)%3B%0A%20%0A%20%20%20%20%2F*%20Advance%20the%20source%20pointer%20*%2F%0A%20%20%20%20*sourceRef%20%3D%20newNode-%3Enext%3B%0A%20%0A%20%20%20%20%2F*%20Link%20the%20old%20dest%20off%20the%20new%20node%20*%2F%0A%20%20%20%20newNode-%3Enext%20%3D%20*destRef%3B%0A%20%0A%20%20%20%20%2F*%20Move%20dest%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20*destRef%20%3D%20newNode%3B%0A%7D%0A%20%0A%20%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%0A%20%20%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20%20%20while%20(node!%3DNULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20node*%20res%20%3D%20NULL%3B%0A%20%20%20%20struct%20node*%20a%20%3D%20NULL%3B%0A%20%20%20%20struct%20node*%20b%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20Let%20us%20create%20two%20sorted%20linked%20lists%20to%20test%0A%20%20%20%20%20%20the%20functions%0A%20%20%20%20%20%20%20Created%20lists%2C%20a%3A%205-%3E10-%3E15%2C%20%20b%3A%202-%3E3-%3E20%20*%2F%0A%20%20%20%20push(%26a%2C%2015)%3B%0A%20%20%20%20push(%26a%2C%2010)%3B%0A%20%20%20%20push(%26a%2C%205)%3B%0A%20%0A%20%20%20%20push(%26b%2C%2020)%3B%0A%20%20%20%20push(%26b%2C%203)%3B%0A%20%20%20%20push(%26b%2C%202)%3B%0A%20%0A%20%20%20%20%2F*%20Remove%20duplicates%20from%20linked%20list%20*%2F%0A%20%20%20%20res%20%3D%20SortedMerge(a%2C%20b)%3B%0A%20%0A%20%20%20%20printf(%22Merged%20Linked%20List%20is%3A%20%5Cn%22)%3B%0A%20%20%20%20printList(res)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output :<\/strong><\/p>\n<pre>Merged Linked List is: \r\n2 3 5 10 15 20 \r\n<\/pre>\n[ad type=\u201dbanner\u201d]\n<p><strong>Method 2 (Using Local References)<\/strong><br \/>\nThis solution is structurally very similar to the above, but it avoids using a dummy node. Instead, it maintains a struct node** pointer, lastPtrRef, that always points to the last pointer of the result list. This solves the same case that the dummy node did \u2014 dealing with the result list when it is empty. If you are trying to build up a list at its tail, either the dummy node or the struct node** \u201creference\u201d strategy can be used (see Section 1 for details).<\/p>\n<div><strong>\u00a0C++ Programming:<\/strong><\/div>\n<div>\n[pastacode lang=\u201dcpp\u201d manual=\u201dstruct%20node*%20SortedMerge(struct%20node*%20a%2C%20struct%20node*%20b)%20%0A%7B%0A%20%20struct%20node*%20result%20%3D%20NULL%3B%0A%20%20%20%0A%20%20%2F*%20point%20to%20the%20last%20result%20pointer%20*%2F%0A%20%20struct%20node**%20lastPtrRef%20%3D%20%26result%3B%20%0A%20%20%20%0A%20%20while(1)%20%0A%20%20%7B%0A%20%20%20%20if%20(a%20%3D%3D%20NULL)%20%0A%20%20%20%20%7B%0A%20%20%20%20%20%20*lastPtrRef%20%3D%20b%3B%0A%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%20if%20(b%3D%3DNULL)%20%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20*lastPtrRef%20%3D%20a%3B%0A%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%7D%0A%20%20%20%20if(a-%3Edata%20%3C%3D%20b-%3Edata)%20%0A%20%20%20%20%7B%0A%20%20%20%20%20%20MoveNode(lastPtrRef%2C%20%26a)%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20MoveNode(lastPtrRef%2C%20%26b)%3B%0A%20%20%20%20%7D%0A%20%20%20%0A%20%20%20%20%2F*%20tricky%3A%20advance%20to%20point%20to%20the%20next%20%22.next%22%20field%20*%2F%0A%20%20%20%20lastPtrRef%20%3D%20%26((*lastPtrRef)-%3Enext)%3B%20%0A%20%20%7D%0A%20%20return(result)%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>Method 3 (Using Recursion)<\/strong><br \/>\nMerge is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code. You probably wouldn\u2019t want to use the recursive version for production code however, because it will use stack space which is proportional to the length of the lists.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201dstruct%20node*%20SortedMerge(struct%20node*%20a%2C%20struct%20node*%20b)%20%0A%7B%0A%20%20struct%20node*%20result%20%3D%20NULL%3B%0A%20%0A%20%20%2F*%20Base%20cases%20*%2F%0A%20%20if%20(a%20%3D%3D%20NULL)%20%0A%20%20%20%20%20return(b)%3B%0A%20%20else%20if%20(b%3D%3DNULL)%20%0A%20%20%20%20%20return(a)%3B%0A%20%0A%20%20%2F*%20Pick%20either%20a%20or%20b%2C%20and%20recur%20*%2F%0A%20%20if%20(a-%3Edata%20%3C%3D%20b-%3Edata)%20%0A%20%20%7B%0A%20%20%20%20%20result%20%3D%20a%3B%0A%20%20%20%20%20result-%3Enext%20%3D%20SortedMerge(a-%3Enext%2C%20b)%3B%0A%20%20%7D%0A%20%20else%0A%20%20%7B%0A%20%20%20%20%20result%20%3D%20b%3B%0A%20%20%20%20%20result-%3Enext%20%3D%20SortedMerge(a%2C%20b-%3Enext)%3B%0A%20%20%7D%0A%20%20return(result)%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>C++ Algorithm &#8211; Merge two sorted linked lists &#8211; Linked List &#8211; Write a Sorted Merge() function that takes two lists, each of which is 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":[72394,81476,81477,81474,81479,81478,81483,81475,81482,81481,81480,81484],"class_list":["post-27369","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-singly-linked-list","tag-bubble-sort-linked-list-c","tag-merge-sort-linked-list-c","tag-merge-two-sorted-array","tag-merge-two-sorted-linked-lists-python","tag-merge-two-sorted-lists-python","tag-merge-two-unsorted-linked-lists","tag-merge-two-unsorted-linked-lists-in-c","tag-merging-of-linked-list-in-data-structure","tag-sort-linked-list-in-c","tag-sorted-linked-list-c","tag-sorted-linked-list-java","tag-sorting-a-singly-linked-list-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27369","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=27369"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27369\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27369"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27369"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27369"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}