{"id":5890,"date":"2021-11-08T11:17:52","date_gmt":"2021-11-08T11:17:52","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5890"},"modified":"2022-03-10T17:40:52","modified_gmt":"2022-03-10T17:40:52","slug":"union-intersection-two-linked-lists-using-merge-sort","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/","title":{"rendered":"Union intersection Two Linked Lists Using Merge Sort"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png\" alt=\"\" \/><\/p>\n<h3>Introduction<\/h3>\n<p>Linked list is one of the most important concepts and data structures to learn while preparing for coding interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.<\/p>\n<\/p>\n<h3>Problem Statement<\/h3>\n<p>According to the problem statement, we are given two singly linked lists, and our task is to find union and Intersection lists of both the given linked lists.<\/p>\n<h4>Input:<\/h4>\n<p><strong>List1:<\/strong> 5\u219219\u219210\u219222\u2192132<br \/>\n<strong>List2:<\/strong> 10\u219211\u219219\u219222\u21926<\/p>\n<h4>Output:<\/h4>\n<p><strong>Intersection List:<\/strong> 10\u219219\u219222<br \/>\n<strong>Union List:<\/strong> 5\u21926\u219210\u219211\u219219\u219222\u2192132<\/p>\n<p><strong>Intersection List<\/strong> contains all the nodes that are common in both the linked list.<\/p>\n<p><strong>Union List<\/strong> contains all the nodes that are present in both the given linked list.<\/p>\n<p>If you are not aware of how to sort a linked list using merge sort, check out this article <a href=\"https:\/\/prepbytes.com\/blog\/linked-list\/merge-sort-on-a-singly-linked-list\/\">Merge sort on a singly-linked list<\/a>.<\/p>\n<h3>Algorithm for Intersection<\/h3>\n<p>1) First, apply merge sort on both the linked lists.<br \/>\n2) Now, Both the lists are sorted.<br \/>\n3) Now, traverse through both the linked lists simultaneously and create an Intersection list for those nodes that are common in both the linked lists.<\/p>\n<h3>Dry Run<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_1-9.jpg\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_2-9.jpg\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_3-7.jpg\" alt=\"\" \/><\/p>\n<h3>Code Implementation<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5891 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_5891 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_5891 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5891 .wpsm_nav-tabs > li.active > a, #tab_container_5891 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5891 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_5891 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_5891 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5891 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5891 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5891 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5891 .wpsm_nav-tabs > li > a:hover , #tab_container_5891 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_5891 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_5891 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_5891 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_5891 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_5891 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_5891 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_5891 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5891 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_5891 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5891 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_5891 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_5891\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5891\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5891_1\" aria-controls=\"tabs_desc_5891_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5891_2\" aria-controls=\"tabs_desc_5891_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_5891\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_5891_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include<bits\/stdc++.h>\r\nusing namespace std;\r\n \r\nclass Node{\r\npublic:\r\n    int data;\r\n    Node* next;\r\n \r\n    Node(int data){\r\n        this->data = data;\r\n        this->next = NULL;\r\n    }\r\n};\r\n \r\n\/* find and return middle node of the linked list*\/\r\nNode* middle(Node* head, Node* tail) {\r\n        Node* slow = head;\r\n        Node* fast = head;\r\n        \r\n        while(fast!=tail && fast->next!=tail){\r\n            slow = slow->next;\r\n            fast = fast->next->next;\r\n        }\r\n        Node* afterMiddle = slow->next;\r\n        slow->next = NULL;\r\n        return afterMiddle;\r\n}\r\n \r\n\/* merge sort*\/\r\nNode* mergeSort(Node* head){\r\n    if(head == NULL || head->next == NULL){\r\n        return head;\r\n    }\r\n \r\n    Node* tail = head;\r\n \r\n    while(tail->next){\r\n        tail = tail->next;\r\n    }\r\n \r\n \r\n    Node* afterMiddle = middle(head, tail);\r\n    Node* part1 = mergeSort(head);\r\n    Node* part2 = mergeSort(afterMiddle);\r\n \r\n    Node *curr1 = part1, *curr2 = part2;\r\n \r\n \r\n    Node *si = NULL, *ei = NULL;\r\n \r\n    while(curr1 && curr2){\r\n        if(curr1->data <= curr2->data){\r\n            if(si == NULL){\r\n                si = curr1;\r\n                ei = curr1;\r\n            }else{\r\n                ei->next = curr1;\r\n                ei = curr1;\r\n            }\r\n            curr1 = curr1->next;\r\n        }else{\r\n            if(si == NULL){\r\n                si = curr2;\r\n                ei = curr2;\r\n            }else{\r\n                ei->next = curr2;\r\n                ei = curr2;\r\n            }\r\n            curr2 = curr2->next;\r\n        }\r\n    }\r\n \r\n \r\n    while(curr1){\r\n        ei->next = curr1;\r\n        ei = curr1;\r\n        curr1 = curr1->next;\r\n    }\r\n \r\n    while(curr2){\r\n        ei->next = curr2;\r\n        ei = curr2;\r\n        curr2 = curr2->next;\r\n    }\r\n \r\n \r\n    return si;\r\n}\r\n\r\n\/* function to print the list *\/\r\nvoid printList(Node* head){\r\n    while(head != NULL){\r\n        cout<<head->data<<\" \";\r\n        head = head->next;\r\n    }\r\n    cout<<endl;\r\n}\r\n \r\n\/* function to find the intersection list *\/\r\nNode* intersectionList(Node* list1, Node* list2){\r\n    if(list1 == NULL || list2==NULL){\r\n        return NULL;\r\n    }\r\n \r\n    Node* intersectionHead = NULL;\r\n    Node* intersectionTail = NULL;\r\n \r\n    while(list1 && list2){\r\n        if(list1->data == list2->data){\r\n            if(intersectionHead == NULL && intersectionTail == NULL){\r\n                intersectionHead = list1;\r\n                intersectionTail = list1;\r\n            }else{\r\n                intersectionTail->next = list1;\r\n                intersectionTail = list1;\r\n            }\r\n            list1 = list1->next;\r\n            list2 = list2->next;\r\n        }else if(list1->data < list2->data){\r\n            list1 = list1->next;\r\n        }else if(list1->data > list2->data){\r\n            list2 = list2->next;\r\n        }\r\n    }\r\n \r\n    intersectionTail->next = NULL;\r\n    return intersectionHead;\r\n}\r\n \r\n\/* function to insert a node at the beginning of a linked list*\/\r\nNode* push(Node* head, int new_data){\r\n \r\n    Node* new_node = new Node(new_data);\r\n \r\n    \/* link the old list with the new node *\/\r\n    new_node->next = head;\r\n \r\n    \/* move the head to point to the new node *\/\r\n    head = new_node;\r\n \r\n    return head;\r\n}\r\n \r\nint main()\r\n{\r\n   \r\n    \/* Start with the empty list *\/\r\n    Node* head1 = NULL;\r\n    Node* head2 = NULL;\r\n    Node* list_intersection = NULL;\r\n \r\n    \/*create a new linked lits 10->15->4->20 *\/\r\n    head1 = push(head1, 20);\r\n    head1 = push(head1, 4);\r\n    head1 = push(head1, 15);\r\n    head1 = push(head1, 10);\r\n \r\n    \/*create a new linked lits 8->4->2->10 *\/\r\n    head2 = push(head2, 10);\r\n    head2 = push(head2, 2);\r\n    head2 = push(head2, 4);\r\n    head2 = push(head2, 8);\r\n    \r\n \r\n    cout << \"First list \" << endl;\r\n    printList(head1);\r\n    cout << \"Second list \" << endl;\r\n    printList(head2);\r\n    \r\n    head1 = mergeSort(head1);\r\n    head2 = mergeSort(head2);\r\n    \r\n    list_intersection = intersectionList(head1, head2);    \r\n    cout << \"Intersection list \" << endl;\r\n    printList(list_intersection);\r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_5891_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nclass Node:\r\n\tdef __init__(self, data):\r\n\t\tself.data = data\r\n\t\tself.next = None\r\n\r\nclass LinkedList:\r\n\t\r\n\tdef __init__(self):\r\n\t\tself.head = None\r\n\r\n\tdef push(self, new_data):\r\n\r\n\t\tnew_node = Node(new_data)\r\n\t\tnew_node.next = self.head\r\n\t\tself.head = new_node\r\n\r\n\r\ndef middle(head, tail):\r\n\r\n\tslow = head\r\n\tfast = head\r\n\r\n\twhile fast != tail and fast.next != tail:\r\n\t\tslow = slow.next\r\n\t\tfast = fast.next.next\r\n\r\n\tafterMiddle = slow.next\r\n\tslow.next = None\r\n\treturn afterMiddle\r\n\r\ndef mergeSort(head):\r\n\r\n\tif head == None or head.next == None:\r\n\t\treturn head\r\n\r\n\ttail = head\r\n\r\n\twhile tail.next:\r\n\t\ttail = tail.next\r\n\r\n\tafterMiddle = middle(head, tail)\r\n\tpart1 = mergeSort(head)\r\n\tpart2 = mergeSort(afterMiddle)\r\n\r\n\tcurr1 = part1\r\n\tcurr2 = part2\r\n\r\n\tsi, ei = None, None\r\n\r\n\twhile curr1 and curr2:\r\n\t\tif curr1.data &lt;= curr2.data:\r\n\t\t\tif si == None:\r\n\t\t\t\tsi = curr1\r\n\t\t\t\tei = curr1\r\n\t\t\telse:\r\n\t\t\t\tei.next = curr1\r\n\t\t\t\tei = curr1\r\n\t\t\tcurr1 = curr1.next\r\n\t\telse:\r\n\t\t\tif si == None:\r\n\t\t\t\tsi = curr2\r\n\t\t\t\tei = curr2\r\n\t\t\telse:\r\n\t\t\t\tei.next = curr2\r\n\t\t\t\tei = curr2\r\n\t\t\tcurr2 = curr2.next\r\n\r\n\twhile curr1:\r\n\t\tei.next = curr1\r\n\t\tei = curr1\r\n\t\tcurr1 = curr1.next\r\n\r\n\twhile curr2:\r\n\t\tei.next = curr2\r\n\t\tei = curr2\r\n\t\tcurr2 = curr2.next\r\n\r\n\treturn si\r\n\r\ndef printList(head):\r\n\twhile head:\r\n\t\tprint(head.data, end=&quot; &quot;)\r\n\t\thead = head.next\r\n\r\ndef intersectionList(head1, head2):\r\n\r\n\tresult = LinkedList()\r\n\tt1 = head1\r\n\tt2 = head2\r\n\r\n\twhile t1 and t2:\r\n\t\tif t1.data &lt; t2.data:\r\n\t\t\tt1 = t1.next\r\n\t\telif t1.data &gt; t2.data:\r\n\t\t\tt2 = t2.next\r\n\t\telse:\r\n\t\t\tresult.push(t2.data)\r\n\t\t\tt1 = t1.next\r\n\t\t\tt2 = t2.next\r\n\r\n\treturn result.head\r\n\r\nhead1 = Node(20)\r\nhead1.next = Node(4)\r\nhead1.next.next = Node(15)\r\nhead1.next.next.next = Node(10)\r\n\r\nhead2 = Node(10)\r\nhead2.next = Node(2)\r\nhead2.next.next = Node(4)\r\nhead2.next.next.next = Node(8)\r\n\r\nhead1 = mergeSort(head1)\r\nhead2 = mergeSort(head2)\r\n\r\nlist_intersection = intersectionList(head1, head2)\r\n\r\nprint(&quot;First list&quot;)\r\nprintList(head1)\r\nprint(&quot;&#92;nSecond list&quot;)\r\nprintList(head2)\r\n\r\nprint(&quot;&#92;nIntersection list&quot;)\r\nprintList(list_intersection)\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_5891 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_5891 a\"),jQuery(\"#tab-content_5891\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<h4>Output<\/h4>\n<p>First list<br \/>\n10 15 4 20<br \/>\nSecond list<br \/>\n8 4 2 10<br \/>\nIntersection list<br \/>\n4 10 <\/p>\n<p><strong>Time Complexity:<\/strong> O(mLogm + nLogn). Since We have applied merge sort on both the linked list.<br \/>\n<strong>Space Complexity:<\/strong> O(n + m). Since We have applied merge sort on both the linked list.<\/p>\n<h3>Algorithm for Union<\/h3>\n<p>1) First, apply merge sort on both the linked lists.<br \/>\n2) Now, Both the lists are sorted.<br \/>\n3) Now, traverse through both the linked lists simultaneously and create a <strong>Union List<\/strong>, which contains all the nodes present in both the linked lists.<\/p>\n<h3>Dry Run<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_4-5.jpg\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_5-4.jpg\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_6_7-1.jpg\" alt=\"\" \/><\/p>\n<h3>Code Implementation<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5893 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_5893 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_5893 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5893 .wpsm_nav-tabs > li.active > a, #tab_container_5893 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5893 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_5893 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_5893 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5893 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5893 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5893 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5893 .wpsm_nav-tabs > li > a:hover , #tab_container_5893 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_5893 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_5893 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_5893 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_5893 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_5893 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_5893 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_5893 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5893 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_5893 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5893 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_5893 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_5893\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5893\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5893_1\" aria-controls=\"tabs_desc_5893_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_5893\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_5893_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include&lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n \r\nclass Node{\r\npublic:\r\n    int data;\r\n    Node* next;\r\n \r\n    Node(int data){\r\n        this-&gt;data = data;\r\n        this-&gt;next = NULL;\r\n    }\r\n};\r\n \r\n\/* find and return middle node of the linked list*\/\r\nNode* middle(Node* head, Node* tail) {\r\n        Node* slow = head;\r\n        Node* fast = head;\r\n        \r\n        while(fast!=tail &amp;&amp; fast-&gt;next!=tail){\r\n            slow = slow-&gt;next;\r\n            fast = fast-&gt;next-&gt;next;\r\n        }\r\n        Node* afterMiddle = slow-&gt;next;\r\n        slow-&gt;next = NULL;\r\n        return afterMiddle;\r\n}\r\n \r\n\/* merge sort*\/\r\nNode* mergeSort(Node* head){\r\n    if(head == NULL || head-&gt;next == NULL){\r\n        return head;\r\n    }\r\n \r\n    Node* tail = head;\r\n \r\n    while(tail-&gt;next){\r\n        tail = tail-&gt;next;\r\n    }\r\n \r\n \r\n    Node* afterMiddle = middle(head, tail);\r\n    Node* part1 = mergeSort(head);\r\n    Node* part2 = mergeSort(afterMiddle);\r\n \r\n    Node *curr1 = part1, *curr2 = part2;\r\n \r\n \r\n    Node *si = NULL, *ei = NULL;\r\n \r\n    while(curr1 &amp;&amp; curr2){\r\n        if(curr1-&gt;data &lt;= curr2-&gt;data){\r\n            if(si == NULL){\r\n                si = curr1;\r\n                ei = curr1;\r\n            }else{\r\n                ei-&gt;next = curr1;\r\n                ei = curr1;\r\n            }\r\n            curr1 = curr1-&gt;next;\r\n        }else{\r\n            if(si == NULL){\r\n                si = curr2;\r\n                ei = curr2;\r\n            }else{\r\n                ei-&gt;next = curr2;\r\n                ei = curr2;\r\n            }\r\n            curr2 = curr2-&gt;next;\r\n        }\r\n    }\r\n \r\n \r\n    while(curr1){\r\n        ei-&gt;next = curr1;\r\n        ei = curr1;\r\n        curr1 = curr1-&gt;next;\r\n    }\r\n \r\n    while(curr2){\r\n        ei-&gt;next = curr2;\r\n        ei = curr2;\r\n        curr2 = curr2-&gt;next;\r\n    }\r\n \r\n \r\n    return si;\r\n}\r\n \r\n\/* print function to print the linked list *\/\r\nvoid printList(Node* head){\r\n    while(head != NULL){\r\n        cout&lt;&lt;head-&gt;data&lt;&lt;&quot; &quot;;\r\n        head = head-&gt;next;\r\n    }\r\n    cout&lt;&lt;endl;\r\n}\r\n \r\n\/* Function to find UNION LIST of two linked lists *\/\r\nNode* unionList(Node* list1, Node* list2){\r\n        \/\/ If both linked list is empty then return NULL\r\n        if(list1 == NULL &amp;&amp; list2==NULL){\r\n        return NULL;\r\n        }\r\n \r\n \r\n        if(list1 != NULL &amp;&amp; list2 == NULL){\r\n            return list1;\r\n        }\r\n \r\n        if(list2 != NULL &amp;&amp; list1 == NULL){\r\n            return list2;\r\n        }\r\n \r\n    Node* uniHead = NULL;\r\n    Node* uniTail = NULL;\r\n \r\n    while(list1 &amp;&amp; list2){\r\n        if(list1-&gt;data == list2-&gt;data){\r\n            if(uniHead == NULL &amp;&amp; uniTail == NULL){\r\n                uniHead = list1;\r\n                uniTail = list1;\r\n            }else{\r\n                uniTail-&gt;next = list1;\r\n                uniTail = list1;\r\n            }\r\n            list1 = list1-&gt;next;\r\n            list2 = list2-&gt;next;\r\n \r\n        }else if(list2-&gt;data &lt; list1-&gt;data){\r\n            if(uniHead == NULL &amp;&amp; uniTail == NULL){\r\n                uniHead = list2;\r\n                uniTail = list2;\r\n            }else{\r\n                uniTail-&gt;next = list2;\r\n                uniTail = list2;\r\n            }\r\n \r\n            list2 = list2-&gt;next;\r\n        }else if(list2-&gt;data &gt; list1-&gt;data){\r\n            if(uniHead == NULL &amp;&amp; uniTail == NULL){\r\n                uniHead = list1;\r\n                uniTail = list1;\r\n            }else{\r\n                uniTail-&gt;next = list1;\r\n                uniTail = list1;\r\n            }\r\n \r\n            list1 = list1-&gt;next;\r\n        }\r\n    }\r\n \r\n    return uniHead;\r\n}\r\n \r\n\/* function to insert a node at the beginning of a linked list*\/\r\nNode* push(Node* head, int new_data){\r\n \r\n    Node* new_node = new Node(new_data);\r\n \r\n    \/* link the old list with the new node *\/\r\n    new_node-&gt;next = head;\r\n \r\n    \/* move the head to point to the new node *\/\r\n    head = new_node;\r\n \r\n    return head;\r\n}\r\n\r\nint main()\r\n{   \r\n    \/* Start with the empty list *\/\r\n    Node* head1 = NULL;\r\n    Node* head2 = NULL;\r\n    Node* list_union = NULL;\r\n \r\n    \/*create a new linked lits 10-&gt;15-&gt;4-&gt;20 *\/\r\n    head1 = push(head1, 20);\r\n    head1 = push(head1, 4);\r\n    head1 = push(head1, 15);\r\n    head1 = push(head1, 10);\r\n \r\n    \/*create a new linked lits 8-&gt;4-&gt;2-&gt;10 *\/\r\n    head2 = push(head2, 10);\r\n    head2 = push(head2, 2);\r\n    head2 = push(head2, 4);\r\n    head2 = push(head2, 8);\r\n    \r\n \r\n    cout &lt;&lt; &quot;First list &quot; &lt;&lt; endl;\r\n    printList(head1);\r\n    cout &lt;&lt; &quot;Second list &quot; &lt;&lt; endl;\r\n    printList(head2);\r\n    \r\n    head1 = mergeSort(head1);\r\n    head2 = mergeSort(head2);\r\n    \r\n    list_union = unionList(head1, head2);\r\n    \r\n    cout &lt;&lt; &quot;Union List &quot; &lt;&lt; endl;\r\n    printList(list_union);\r\n \r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_5893 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_5893 a\"),jQuery(\"#tab-content_5893\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<h4>Output<\/h4>\n<p>First list<br \/>\n10 15 4 20<br \/>\nSecond list<br \/>\n8 4 2 10<br \/>\nUnion List<br \/>\n2 4 8 10 15 20 <\/p>\n<p><strong>Time Complexity:<\/strong> O(mLogm + nLogn). Since We have applied merge sort on both the linked list.<br \/>\n<strong>Space Complexity:<\/strong> O(n + m). Since We have applied merge sort on both the linked list.<\/p>\n<p>So, In this blog, we have learned How to find the Union and Intersection of two linked lists using Merge Sort. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction Linked list is one of the most important concepts and data structures to learn while preparing for coding interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview. Problem Statement According to the problem statement, we are given two singly linked lists, and our task is [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[125],"tags":[],"class_list":["post-5890","post","type-post","status-publish","format-standard","hentry","category-linked-list"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Union intersection Two Linked Lists Using Merge Sort | Linked list articles | PrepBytes Blog<\/title>\n<meta name=\"description\" content=\"Learn how to find Union and Intersection of two Linked Lists Using Merge Sort.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Union intersection Two Linked Lists Using Merge Sort | Linked list articles | PrepBytes Blog\" \/>\n<meta property=\"og:description\" content=\"Learn how to find Union and Intersection of two Linked Lists Using Merge Sort.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-11-08T11:17:52+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-03-10T17:40:52+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png\" \/>\n<meta name=\"author\" content=\"PrepBytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"PrepBytes\" \/>\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:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/\"},\"author\":{\"name\":\"PrepBytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\"},\"headline\":\"Union intersection Two Linked Lists Using Merge Sort\",\"datePublished\":\"2021-11-08T11:17:52+00:00\",\"dateModified\":\"2022-03-10T17:40:52+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/\"},\"wordCount\":371,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/\",\"name\":\"Union intersection Two Linked Lists Using Merge Sort | Linked list articles | PrepBytes Blog\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png\",\"datePublished\":\"2021-11-08T11:17:52+00:00\",\"dateModified\":\"2022-03-10T17:40:52+00:00\",\"description\":\"Learn how to find Union and Intersection of two Linked Lists Using Merge Sort.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linked list articles\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/linked-list\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Union intersection Two Linked Lists Using Merge Sort\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\",\"name\":\"PrepBytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"caption\":\"PrepBytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Union intersection Two Linked Lists Using Merge Sort | Linked list articles | PrepBytes Blog","description":"Learn how to find Union and Intersection of two Linked Lists Using Merge Sort.","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:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/","og_locale":"en_US","og_type":"article","og_title":"Union intersection Two Linked Lists Using Merge Sort | Linked list articles | PrepBytes Blog","og_description":"Learn how to find Union and Intersection of two Linked Lists Using Merge Sort.","og_url":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-11-08T11:17:52+00:00","article_modified_time":"2022-03-10T17:40:52+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png","type":"","width":"","height":""}],"author":"PrepBytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PrepBytes","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/"},"author":{"name":"PrepBytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e"},"headline":"Union intersection Two Linked Lists Using Merge Sort","datePublished":"2021-11-08T11:17:52+00:00","dateModified":"2022-03-10T17:40:52+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/"},"wordCount":371,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/","url":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/","name":"Union intersection Two Linked Lists Using Merge Sort | Linked list articles | PrepBytes Blog","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png","datePublished":"2021-11-08T11:17:52+00:00","dateModified":"2022-03-10T17:40:52+00:00","description":"Learn how to find Union and Intersection of two Linked Lists Using Merge Sort.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012373884-Article_209.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/union-intersection-two-linked-lists-using-merge-sort\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Linked list articles","item":"https:\/\/prepbytes.com\/blog\/category\/linked-list\/"},{"@type":"ListItem","position":3,"name":"Union intersection Two Linked Lists Using Merge Sort"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e","name":"PrepBytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","caption":"PrepBytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5890","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=5890"}],"version-history":[{"count":6,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5890\/revisions"}],"predecessor-version":[{"id":7934,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5890\/revisions\/7934"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=5890"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=5890"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=5890"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}