{"id":1361,"date":"2024-01-09T15:00:00","date_gmt":"2024-01-09T15:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1361"},"modified":"2024-01-11T10:22:41","modified_gmt":"2024-01-11T10:22:41","slug":"intersection-of-two-linked-lists","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/intersection-of-two-linked-lists\/","title":{"rendered":"Intersection of Two Linked Lists (C++, Java, Python)"},"content":{"rendered":"\n<p>In the world of linked lists, there are often situations where two lists intersect. By intersecting, it means that the two lists share a common node from a certain point onwards. This can occur due to programming errors or intentional design choices. In this article, we will try to find the intersection of two linked lists from basic brute force to an optimized approach.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Intersection of Two Linked Lists Problem<\/strong><\/h2>\n\n\n\n<p><strong>In the Intersection of Two Linked Lists problem, we are given two singly linked lists, let&#8217;s call them List 1 and List 2. These lists might have different lengths, and they intersect at some point. Our goal is to develop an algorithm that can efficiently identify the node at which the two lists intersect.&nbsp;<\/strong><\/p>\n\n\n\n<p>Let&#8217;s see an example.<\/p>\n\n\n\n<p><strong>Input:<\/strong> List 1 = [1,3,1,2,4], List 2 = [1,3,2,4]<\/p>\n\n\n\n<p><strong>Output:<\/strong> 2<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/Q3uX_4u6WwJBiFqXTmFMtS_XdFcMBC0cfWMyQF82dJYNujH_oC9q2X2kmaC9YIztVOSr_hPmYICrnuD0Kw0DBBfaHWt2f-HYXNJaMHtVlLZKd2yXohkRm_bG4TzM9ifW8lMKsWzi9hAxXBfN3tvLkb4\" alt=\"Example of Intersection of Two Linked Lists\"\/><\/figure>\n<\/div>\n\n\n<p>As we can see both the linked lists intersect at node 2.<\/p>\n\n\n\n<p>In the simple brute-force approach, we will iterate through one of the lists and check if each node exists in the other list. If we find a common node, we have found the intersection point. Below are the steps involved:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Firstly we will choose any of the lists and iterate through its nodes.<\/li>\n\n\n\n<li>For each node in List 1, iterate through List 2 and compare each node with the current node from List 1.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/StznSzvQsanUY3VQj2X5Rgd3wg0WSZVpOlI1ICKSAvyneZyQBaKBLbM3-d1l0O-GCDfnco4_nb9cv7WAdPwLvRbCE50k4U8sKGdI60adb_d3pMC1ri2EBF3avVYRl0i4ICNWOssiFNd1H_k9jKgj6wg\" alt=\"Compare first node\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If we find a matching node, we have found an intersection point then we will return that node.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/SVajJ3-T-L4HQWwohNW21ko4eoln9r6e7m_cbSevPuuq7MCJS1T0G1MtVxj2keUsIqXD000IZ8AovaP6gRHzL0di60fiTXNIBp9-47VEUBA_8yvEcYzrrJJCASV-mAPsnl14jHuCbH4G7f2z3rT79do\" alt=\"Found an intersection point\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If we complete the iteration of List 2 without finding a matching node, there is no intersection between the lists. Return null.<\/li>\n<\/ul>\n\n\n\n<p>The time complexity is O(m*n) because, for each node in list 2, entire lists 1 are iterated.&nbsp;The space complexity is O(1) as no extra space is required.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Hashing to Find Intersection of Two Linked Lists<\/strong><\/h2>\n\n\n\n<p><strong>The best solution to find the intersection of two linked lists is by using hashing. We will use a hash set to keep track of nodes so that when we find a common node.&nbsp;<\/strong><\/p>\n\n\n\n<p>Here are the steps used in this approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Create a hash table to keep check of the nodes.<\/li>\n\n\n\n<li>Firstly we will Iterate through list 1 and hash its node address.<\/li>\n\n\n\n<li>Then we will iterate through list 2 and search the hashed value in the hash table.<\/li>\n\n\n\n<li>If we find any node address then we will return that node.<\/li>\n<\/ul>\n\n\n\n<p>The Time Complexity is O(n+m) because iterating through list 1 first takes O(n), then iterating through list 2 takes O(m).&nbsp; The Space Complexity is O(n) because storing list 1 node addresses in unordered_set. Learn more about <a href=\"https:\/\/favtutor.com\/blogs\/hashing-in-data-structure\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/hashing-in-data-structure\">Hashing in this guide here<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Optimized Approach<\/strong><\/h3>\n\n\n\n<p>In this approach, we will follow the following steps:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will take two dummy nodes and point each to the head of the lists.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/rrY14RHsA1yZmoN1gkJsxrwvkre10wSc3p5jpFOg1jJUeDTjrAKMhZs0QkYJTvIdM9-RVIt__qHIoOf751J0jU9r5KuilI6fVRHKUWpFufVEELMAtXS-ev2fUpXPZReEliqUM5cT52OsAThL3y2c_oc\" alt=\"take two dummy nodes\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will iterate over them. If anyone becomes null, we will point them to the head of the opposite list and continue iterating until they collide.<\/li>\n<\/ul>\n\n\n\n<p>Let\u2019s try to understand this approach with an example:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/b5zTpGPABkeDQn40DMK1r-vbybTx-jw0mFMTultV6e2sDetha_AGOm2yWaQ3qlWTKddRQfyAxk7TkLa20sqLzCNqF_M9I_4BnXk8IxOq6wPCjh4m4KSLmbyY6YAIYCTTB_Fk_0wx0qLjuwtkvcTSTZA\" alt=\"After first iteration\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>After 2 iterations head 2 will come to NULL.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/fxZMkXDXYutz_h9Y9BmDQAXyVtufS5CnFGBZQawRpGqz1O95DtWywnAMH_EKoY3VtZEirrTXxkTmRGQ-yCns8b0SSRbINioV_Ir22IIfmGSvDRj3L51gNvXLbZjFdI6sONKiIlinsk44zkjMqmVlSFw\" alt=\"After 2 iterations\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will point head 2 to the opposite list.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/fmK0WlT4uKBDGBMhtRqzWDX0Exe22yMUioZk0Voo-dXUz2TVeVgqpTTQoHCPJjxragY4NwxHQ5KVthNV0MAEAlTgu2H2aJ_XE-GKUqZOEi65PytEp6vHQpvJgwU0afElJ-Tqt-bnb94esRWXl60iP-8\" alt=\"Point head2 to opposite list\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will point head 1 to the opposite list.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/f32cQCrHd_-NOt9ouyd6QgO3ueq5piTbrKzlD97-QWmy-k_djUafPHNPVJOGrhYycusQaOEfS3ZdNDb8KNRnYwPuBNsyUMIspTswQ87rnBLL0x0djLlWy9eEhpc3_PfxNKkl5hqR4G6Pk40U1YkXNI4\" alt=\"Point head1 to opposite list\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now after 2 iterations, both heads will meet at the intersection point.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/asfmdaCSe1fAgT8e0YPk-aMHa57DimUoGE4nfOFB3kENCrF-BaY5hXgpOc9mK_FOnut9avRHWjn5cIZMP3Caxmk6BLMDn0JU6oUMYp9yMSSS1JutShewg1WT19Jf8SlQuUwUXP4kDmLdMr0stONJJjs\" alt=\"intersection point\"\/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Below is the C++ program to find intersection of two linked lists:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nclass node {\npublic:\n    int num;\n    node* next;\n    node(int val) {\n        num = val;\n        next = NULL;\n    }\n};\n\n\/\/ Utility function to insert node at the end of the linked list\nvoid insertNode(node* &amp;head, int val) {\n    node* newNode = new node(val);\n\n    if (head == NULL) {\n        head = newNode;\n        return;\n    }\n\n    node* temp = head;\n    while (temp-&gt;next != NULL) temp = temp-&gt;next;\n\n    temp-&gt;next = newNode;\n    return;\n}\n\n\/\/ Utility function to check presence of intersection\nnode* intersectionPresent(node* head1, node* head2) {\n    node* d1 = head1;\n    node* d2 = head2;\n\n    while (d1 != d2) {\n        d1 = (d1 == NULL) ? head2 : d1-&gt;next;\n        d2 = (d2 == NULL) ? head1 : d2-&gt;next;\n    }\n\n    return d1;\n}\n\n\/\/ Utility function to print linked list\nvoid printList(node* head) {\n    while (head-&gt;next != NULL) {\n        cout &lt;&lt; head-&gt;num &lt;&lt; &quot;-&gt;&quot;;\n        head = head-&gt;next;\n    }\n    cout &lt;&lt; head-&gt;num &lt;&lt; endl;\n}\n\nint main() {\n    \/\/ Creation of both lists\n    node* head = NULL;\n    insertNode(head, 1);\n    insertNode(head, 3);\n    insertNode(head, 1);\n    insertNode(head, 2);\n    insertNode(head, 4);\n    node* head1 = head;\n    head = head-&gt;next-&gt;next-&gt;next;\n\n    \/\/ Create the second list\n    node* headSec = NULL;\n    insertNode(headSec, 1);\n    insertNode(headSec, 3);\n   \n    node* head2 = headSec;\n    headSec-&gt;next-&gt;next = head; \/\/ Connect the last node to the intersection point\n\n    \/\/ Printing of the lists\n    cout &lt;&lt; &quot;List1: &quot;;\n    printList(head1);\n    cout &lt;&lt; &quot;List2: &quot;;\n    printList(head2);\n\n    \/\/ Checking if intersection is present\n    node* answerNode = intersectionPresent(head1, head2);\n    if (answerNode == NULL)\n        cout &lt;&lt; &quot;No intersection\\n&quot;;\n    else\n        cout &lt;&lt; &quot;The intersection point is &quot; &lt;&lt; answerNode-&gt;num &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>You can do it in Java as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.*;\n\nclass Node {\n    int num;\n    Node next;\n\n    Node(int val) {\n        num = val;\n        next = null;\n    }\n}\n\nclass Favtutor {\n    \/\/ Utility function to insert node at the end of the linked list\n    static Node insertNode(Node head, int val) {\n        Node newNode = new Node(val);\n\n        if (head == null) {\n            head = newNode;\n            return head;\n        }\n\n        Node temp = head;\n        while (temp.next != null)\n            temp = temp.next;\n\n        temp.next = newNode;\n        return head;\n    }\n\n    \/\/ Utility function to check the presence of intersection\n    static Node intersectionPresent(Node head1, Node head2) {\n        Node d1 = head1;\n        Node d2 = head2;\n\n        while (d1 != d2) {\n            d1 = (d1 == null) ? head2 : d1.next;\n            d2 = (d2 == null) ? head1 : d2.next;\n        }\n\n        return d1;\n    }\n\n    \/\/ Utility function to print linked list created\n    static void printList(Node head) {\n        while (head.next != null) {\n            System.out.print(head.num + &quot;-&gt;&quot;);\n            head = head.next;\n        }\n        System.out.println(head.num);\n    }\n\n    public static void main(String args[]) {\n        \/\/ Creation of both lists\n        Node head = null;\n        head = insertNode(head, 1);\n        head = insertNode(head, 3);\n        head = insertNode(head, 1);\n        head = insertNode(head, 2);\n        head = insertNode(head, 4);\n        Node head1 = head;\n        head = head.next.next.next;\n\n        \/\/ Creation of the second list\n        Node headSec = null;\n        headSec = insertNode(headSec, 1);\n        headSec = insertNode(headSec, 3);\n        Node head2 = headSec;\n        headSec.next.next = head; \/\/ Connect the last node to the intersection point\n\n        \/\/ Printing of the lists\n        System.out.print(&quot;List1: &quot;);\n        printList(head1);\n        System.out.print(&quot;List2: &quot;);\n        printList(head2);\n\n        \/\/ Checking if intersection is present\n        Node answerNode = intersectionPresent(head1, head2);\n        if (answerNode == null)\n            System.out.println(&quot;No intersection\\n&quot;);\n        else\n            System.out.println(&quot;The intersection point is &quot; + answerNode.num);\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Here is the Python solution:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">class Node:\n    def __init__(self, val):\n        self.val = val\n        self.next = None\n\n# Utility function to insert a node at the end of the linked list\ndef insertNode(head, val):\n    newNode = Node(val)\n    if head is None:\n        head = newNode\n        return head\n    temp = head\n    while temp.next is not None:\n        temp = temp.next\n    temp.next = newNode\n    return head\n\n# Utility function to check the presence of an intersection\ndef intersectionPresent(head1, head2):\n    d1 = head1\n    d2 = head2\n    while d1 != d2:\n        # If d1 reaches the end, reset to head2, else move to the next node\n        d1 = head2 if d1 is None else d1.next\n        # If d2 reaches the end, reset to head1, else move to the next node\n        d2 = head1 if d2 is None else d2.next\n    return d1\n\n# Utility function to print the linked list\ndef printList(head):\n    while head.next is not None:\n        print(head.val, end=' -&gt; ')\n        head = head.next\n    print(head.val)\n\nif __name__ == '__main__':\n    # Creation of the first linked list\n    head = None\n    head = insertNode(head, 1)\n    head = insertNode(head, 3)\n    head = insertNode(head, 1)\n    head = insertNode(head, 2)\n    head = insertNode(head, 4)\n    head1 = head\n    head = head.next.next.next\n\n    # Creation of the second linked list\n    headSec = None\n    headSec = insertNode(headSec, 1)\n    headSec = insertNode(headSec, 3)\n    head2 = headSec\n    headSec.next.next = head  # Connect the last node to the intersection point\n\n    # Printing the linked lists\n    print('List1: ', end='')\n    printList(head1)\n    print('List2: ', end='')\n    printList(head2)\n\n    # Checking if intersection is present\n    answerNode = intersectionPresent(head1, head2)\n    if answerNode is None:\n        print('No intersection')\n    else:\n        print('The intersection point is', answerNode.val)<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>List1: 1 -&gt; 3 -&gt; 1 -&gt; 2 -&gt; 4\nList2: 1 -&gt; 3 -&gt; 2 -&gt; 4\nThe intersection point is 2<\/code><\/pre>\n\n\n\n<p>The Time Complexity is O(2*max(length of list1, length of list2)) because the length of the longer list is traversed twice. The Space Complexity is O(1) because no extra space is used.<\/p>\n\n\n\n<p>Finally, here is a comparison of all the three approaches:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Approach&nbsp;<\/strong><\/td><td><strong>Time complexity<\/strong><\/td><td><strong>Space complexity<\/strong><\/td><td><strong>Details&nbsp;<\/strong><\/td><\/tr><tr><td>Brute force approach<\/td><td>O(m*n)&nbsp;<\/td><td>O(1)<\/td><td>For each node in list 2, entire lists 1 are iterated.&nbsp;<\/td><\/tr><tr><td>Hashing Approach<\/td><td>O(n+m)&nbsp;<\/td><td>O(n)<\/td><td>Iterating through list 1 first takes O(n), then iterating through list 2 takes O(m).&nbsp;<\/td><\/tr><tr><td>Optimized&nbsp; Approach<\/td><td>O(2*max(length of list1,length of list2))<\/td><td>O(1)<\/td><td>length of longer list is traversed twice<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, we have discussed three approaches to finding the intersection of two linked lists, a commonly asked <a href=\"https:\/\/leetcode.com\/problems\/intersection-of-two-linked-lists\/\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/intersection-of-two-linked-lists\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> in technical interviews. We found that traversing through the length of both linked lists optimally helps us to solve this problem more efficiently.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We will solve the leetcode problem to find the intersection of the two linked lists, with implementation in C++, Java and Python.<\/p>\n","protected":false},"author":12,"featured_media":1363,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1361","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1361","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1361"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1361\/revisions"}],"predecessor-version":[{"id":1380,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1361\/revisions\/1380"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1363"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}