{"id":17760,"date":"2022-10-27T00:24:57","date_gmt":"2022-10-26T18:54:57","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/"},"modified":"2022-10-27T00:24:57","modified_gmt":"2022-10-26T18:54:57","slug":"solved-how-to-merge-two-sorted-linked-lists-in-python-closed","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/","title":{"rendered":"[Solved] how to merge two sorted linked lists in python [closed]"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

This operation is just doing the “merge” step of a Merge Sort<\/a> and can be done in O(l1+l2)<\/code> time.<\/p>\n

The general premise is to iterate over both (already sorted) lists at the same time, but only advance the list with the lowest head value, while using the advanced value in the resulting output. The operation is complete when both source lists are exhausted.<\/p>\n

Here is some pseudo-code<\/a> (courtesy of the Wikipedia) and shouldn’t be too hard to translate for a linked list data-type. When implementing it for a linked list a new list can either be created or one of the lists can be destructively modified.<\/p>\n

function merge(left, right)\n    \/\/ receive the left and right sublist as arguments.\n    \/\/ 'result' variable for the merged result of two sublists.\n    var list result\n    \/\/ assign the element of the sublists to 'result' variable until there is no element to merge. \n    while length(left) > 0 or length(right) > 0\n        if length(left) > 0 and length(right) > 0\n           \/\/ compare the first two element, which is the small one, of each two sublists.\n            if first(left) <= first(right)\n                \/\/ the small element is copied to 'result' variable.\n                \/\/ delete the copied one(a first element) in the sublist.\n                append first(left) to result\n                left = rest(left)\n            else\n                \/\/ same operation as the above(in the right sublist).\n                append first(right) to result\n                right = rest(right)\n        else if length(left) > 0\n            \/\/ copy all of remaining elements from the sublist to 'result' variable, \n            \/\/ when there is no more element to compare with.\n            append first(left) to result\n            left = rest(left)\n        else if length(right) > 0\n            \/\/ same operation as the above(in the right sublist).\n            append first(right) to result\n            right = rest(right)\n    end while\n    \/\/ return the result of the merged sublists(or completed one, finally).\n    \/\/ the length of the left and right sublists will grow bigger and bigger, after the next call of this function.\n    return result\n<\/code><\/pre>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            7<\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved how to merge two sorted linked lists in python [closed] <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] This operation is just doing the “merge” step of a Merge Sort and can be done in O(l1+l2) time. The general premise is to iterate over both (already sorted) lists at the same time, but only advance the list with the lowest head value, while using the advanced value in the resulting output. The … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[1402,540,460,349,561],"class_list":["post-17760","post","type-post","status-publish","format-standard","hentry","category-solved","tag-linked-list","tag-list","tag-merge","tag-python","tag-sorting"],"yoast_head":"\n[Solved] how to merge two sorted linked lists in python [closed] - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] how to merge two sorted linked lists in python [closed] - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] This operation is just doing the “merge” step of a Merge Sort and can be done in O(l1+l2) time. The general premise is to iterate over both (already sorted) lists at the same time, but only advance the list with the lowest head value, while using the advanced value in the resulting output. The ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-10-26T18:54:57+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] how to merge two sorted linked lists in python [closed]\",\"datePublished\":\"2022-10-26T18:54:57+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/\"},\"wordCount\":130,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"linked-list\",\"list\",\"merge\",\"python\",\"sorting\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/\",\"name\":\"[Solved] how to merge two sorted linked lists in python [closed] - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-10-26T18:54:57+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] how to merge two sorted linked lists in python [closed]\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] how to merge two sorted linked lists in python [closed] - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] how to merge two sorted linked lists in python [closed] - JassWeb","og_description":"[ad_1] This operation is just doing the “merge” step of a Merge Sort and can be done in O(l1+l2) time. The general premise is to iterate over both (already sorted) lists at the same time, but only advance the list with the lowest head value, while using the advanced value in the resulting output. The ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/","og_site_name":"JassWeb","article_published_time":"2022-10-26T18:54:57+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] how to merge two sorted linked lists in python [closed]","datePublished":"2022-10-26T18:54:57+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/"},"wordCount":130,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["linked-list","list","merge","python","sorting"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/","url":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/","name":"[Solved] how to merge two sorted linked lists in python [closed] - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-10-26T18:54:57+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-how-to-merge-two-sorted-linked-lists-in-python-closed\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] how to merge two sorted linked lists in python [closed]"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/17760","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=17760"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/17760\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=17760"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=17760"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=17760"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}