{"id":670,"date":"2025-07-15T13:58:43","date_gmt":"2025-07-15T08:28:43","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=670"},"modified":"2025-07-15T13:58:46","modified_gmt":"2025-07-15T08:28:46","slug":"intersection-of-two-linked-lists-leetcode-160","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/","title":{"rendered":"Intersection of Two Linked Lists | Leetcode 160 | Brute, Better and Optimal Solutions"},"content":{"rendered":"\n<p>Given the heads of two singly linked-lists&nbsp;<code>headA<\/code>&nbsp;and&nbsp;<code>headB<\/code>, return&nbsp;<em>the node at which the two lists intersect<\/em>. If the two linked lists have no intersection at all, return&nbsp;<code>null<\/code>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/intersection-of-two-linked-lists\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p>For example, the following two linked lists begin to intersect at node&nbsp;<code>c1<\/code>:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/05\/160_statement.png\" alt=\"\"\/><\/figure>\n\n\n\n<p>The test cases are generated such that there are no cycles anywhere in the entire linked structure.<\/p>\n\n\n\n<p><strong>Note<\/strong>&nbsp;that the linked lists must&nbsp;<strong>retain their original structure<\/strong>&nbsp;after the function returns.<\/p>\n\n\n\n<p><strong>Custom Judge:<\/strong><\/p>\n\n\n\n<p>The inputs to the&nbsp;<strong>judge<\/strong>&nbsp;are given as follows (your program is&nbsp;<strong>not<\/strong>&nbsp;given these inputs):<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>intersectVal<\/code>&nbsp;&#8211; The value of the node where the intersection occurs. This is&nbsp;<code>0<\/code>&nbsp;if there is no intersected node.<\/li>\n\n\n\n<li><code>listA<\/code>&nbsp;&#8211; The first linked list.<\/li>\n\n\n\n<li><code>listB<\/code>&nbsp;&#8211; The second linked list.<\/li>\n\n\n\n<li><code>skipA<\/code>&nbsp;&#8211; The number of nodes to skip ahead in&nbsp;<code>listA<\/code>&nbsp;(starting from the head) to get to the intersected node.<\/li>\n\n\n\n<li><code>skipB<\/code>&nbsp;&#8211; The number of nodes to skip ahead in&nbsp;<code>listB<\/code>&nbsp;(starting from the head) to get to the intersected node.<\/li>\n<\/ul>\n\n\n\n<p>The judge will then create the linked structure based on these inputs and pass the two heads,&nbsp;<code>headA<\/code>&nbsp;and&nbsp;<code>headB<\/code>&nbsp;to your program. If you correctly return the intersected node, then your solution will be&nbsp;<strong>accepted<\/strong>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/05\/160_example_1_1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3<br><strong>Output:<\/strong> Intersected at '8'<br><strong>Explanation:<\/strong> The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).<br>From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.<br>- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2<sup>nd<\/sup> node in A and 3<sup>rd<\/sup> node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3<sup>rd<\/sup> node in A and 4<sup>th<\/sup> node in B) point to the same location in memory.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/05\/160_example_2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1<br><strong>Output:<\/strong> Intersected at '2'<br><strong>Explanation:<\/strong> The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).<br>From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/05\/160_example_3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2<br><strong>Output:<\/strong> No intersection<br><strong>Explanation:<\/strong> From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.<br>Explanation: The two lists do not intersect, so return null.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The number of nodes of&nbsp;<code>listA<\/code>&nbsp;is in the&nbsp;<code>m<\/code>.<\/li>\n\n\n\n<li>The number of nodes of&nbsp;<code>listB<\/code>&nbsp;is in the&nbsp;<code>n<\/code>.<\/li>\n\n\n\n<li><code>1 &lt;= m, n &lt;= 3 * 10<sup>4<\/sup><\/code><\/li>\n\n\n\n<li><code>1 &lt;= Node.val &lt;= 10<sup>5<\/sup><\/code><\/li>\n\n\n\n<li><code>0 &lt;= skipA &lt;= m<\/code><\/li>\n\n\n\n<li><code>0 &lt;= skipB &lt;= n<\/code><\/li>\n\n\n\n<li><code>intersectVal<\/code>&nbsp;is&nbsp;<code>0<\/code>&nbsp;if&nbsp;<code>listA<\/code>&nbsp;and&nbsp;<code>listB<\/code>&nbsp;do not intersect.<\/li>\n\n\n\n<li><code>intersectVal == listA[skipA] == listB[skipB]<\/code>&nbsp;if&nbsp;<code>listA<\/code>&nbsp;and&nbsp;<code>listB<\/code>&nbsp;intersect.<\/li>\n<\/ul>\n\n\n\n<p><strong>Follow up:<\/strong>&nbsp;Could you write a solution that runs in&nbsp;<code>O(m + n)<\/code>&nbsp;time and use only&nbsp;<code>O(1)<\/code>&nbsp;memory?<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-03ee7fc8-cc70-409c-b4f1-c19c126babef\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"false\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#0-solution-1-brute-force-approach-using-set\" style=\"\">Solution 1: Brute Force Approach (Using Set)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#8-solution-2-better-approach-length-calculation-alignment\" style=\"\">Solution 2: Better Approach (Length Calculation + Alignment)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#16-solution-3-optimal-approach-two-pointers-with-list-switching\" style=\"\">Solution 3: Optimal Approach (Two Pointers with List Switching)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#17-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#18-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#19-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#20-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#21-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#22-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#23-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/#24-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-using-set\">Solution 1: Brute Force Approach (Using Set)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like finding a common friend between two groups of people! One simple way is to write down all the names from the first group, then go through the second group and check if anyone&#8217;s name is already on your list. The first person you find who&#8217;s on both lists is your common friend. We use the same idea here &#8211; store all nodes from the first list, then check if any node from the second list is already stored.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Create a Storage<\/strong>: Use a set to store all nodes from the first linked list<\/li>\n\n\n\n<li><strong>First Pass<\/strong>: Walk through the first list and add every node to the set<\/li>\n\n\n\n<li><strong>Second Pass<\/strong>: Walk through the second list and check if each node exists in the set<\/li>\n\n\n\n<li><strong>Found Intersection<\/strong>: The first node from the second list that exists in the set is our intersection<\/li>\n\n\n\n<li><strong>No Intersection<\/strong>: If we reach the end of the second list without finding any common node, return null<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def getIntersectionNode(\n        self, headA: ListNode, headB: ListNode\n    ) -&gt; Optional[ListNode]:\n        all_nodes = set()  # Set to store all nodes from first list\n        temp = headA\n        \n        # First pass: Store all nodes from list A\n        while temp:\n            all_nodes.add(temp)  # Add current node to set\n            temp = temp.next\n        \n        temp = headB\n        \n        # Second pass: Check each node of list B in the set\n        while temp:\n            if temp in all_nodes:  # Found intersection!\n                return temp\n            temp = temp.next\n        \n        return None  # No intersection found\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">getIntersectionNode<\/span><span style=\"color: #D4D4D4\">(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">headA<\/span><span style=\"color: #D4D4D4\">: ListNode, <\/span><span style=\"color: #9CDCFE\">headB<\/span><span style=\"color: #D4D4D4\">: ListNode<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    ) -&gt; Optional[ListNode]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        all_nodes = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()  <\/span><span style=\"color: #6A9955\"># Set to store all nodes from first list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = headA<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># First pass: Store all nodes from list A<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            all_nodes.add(temp)  <\/span><span style=\"color: #6A9955\"># Add current node to set<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = headB<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Second pass: Check each node of list B in the set<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> all_nodes:  <\/span><span style=\"color: #6A9955\"># Found intersection!<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> temp<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># No intersection found<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>We use two separate loops here. In the first loop, we walk through the entire first linked list and store every node in a set. Sets are perfect for this because they allow fast lookups. In the second loop, we walk through the second linked list and check if each node already exists in our set. The moment we find a node that&#8217;s already in the set, we&#8217;ve found our intersection point. If we finish the second loop without finding any common nodes, the lists don&#8217;t intersect.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through two lists that intersect:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>List A:&nbsp;<code>1 -&gt; 2 -&gt; 8 -&gt; 4 -&gt; 5<\/code><\/li>\n\n\n\n<li>List B:&nbsp;<code>3 -&gt; 6 -&gt; 8 -&gt; 4 -&gt; 5<\/code>&nbsp;(they share nodes 8, 4, 5)<\/li>\n<\/ul>\n\n\n\n<p><strong>First Pass (Store List A nodes):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit node 1: all_nodes = {1}<\/li>\n\n\n\n<li>Visit node 2: all_nodes = {1, 2}<\/li>\n\n\n\n<li>Visit node 8: all_nodes = {1, 2, 8}<\/li>\n\n\n\n<li>Visit node 4: all_nodes = {1, 2, 8, 4}<\/li>\n\n\n\n<li>Visit node 5: all_nodes = {1, 2, 8, 4, 5}<\/li>\n<\/ul>\n\n\n\n<p><strong>Second Pass (Check List B nodes):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit node 3: 3 not in set, continue<\/li>\n\n\n\n<li>Visit node 6: 6 not in set, continue<\/li>\n\n\n\n<li>Visit node 8: 8 found in set! Return node 8<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;Intersection at node 8<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(m + n) &#8211; We visit each node from both lists once<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(m) &#8211; We store all nodes from the first list in the set<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like keeping a guest list for a party. You write down everyone from the first group, then when people from the second group arrive, you check if their name is already on the list. The first person you recognize is your answer!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-better-approach-length-calculation-alignment\">Solution 2: Better Approach (Length Calculation + Alignment)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Imagine two people walking towards each other from different starting points on converging paths. If one person starts farther away, they need a head start to meet at the same time. Similarly, if our linked lists have different lengths, we can give the longer list a &#8220;head start&#8221; by moving its pointer forward until both lists have the same remaining length. Then we can walk both pointers together until they meet!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Calculate Lengths<\/strong>: Find the length of both linked lists and their last nodes<\/li>\n\n\n\n<li><strong>Check Possibility<\/strong>: If the last nodes are different, the lists don&#8217;t intersect<\/li>\n\n\n\n<li><strong>Align Starting Points<\/strong>: Move the pointer of the longer list forward by the difference in lengths<\/li>\n\n\n\n<li><strong>Walk Together<\/strong>: Move both pointers one step at a time until they meet<\/li>\n\n\n\n<li><strong>Found Intersection<\/strong>: When both pointers point to the same node, that&#8217;s our intersection<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def getIntersectionNode(\n        self, headA: ListNode, headB: ListNode\n    ) -&gt; Optional[ListNode]:\n        lenA = 0\n        lenB = 0\n        lastNodeofA = None\n        lastNodeofB = None\n        temp = headA\n        \n        # Calculate length of list A and find its last node\n        while temp:\n            lenA += 1\n            if temp.next is None:\n                lastNodeofA = temp  # Store last node of A\n            temp = temp.next\n        \n        temp = headB\n        \n        # Calculate length of list B and find its last node\n        while temp:\n            lenB += 1\n            if temp.next is None:\n                lastNodeofB = temp  # Store last node of B\n            temp = temp.next\n        \n        # If last nodes are different, no intersection exists\n        if lastNodeofA is not lastNodeofB:\n            return None\n        \n        diff = abs(lenA - lenB)  # Calculate difference in lengths\n        \n        # Align starting points based on which list is longer\n        if lenA &gt; lenB:\n            temp = headA\n            # Move pointer of longer list forward by difference\n            while diff &gt; 0:\n                temp = temp.next\n                diff -= 1\n            # Walk both pointers together until they meet\n            while temp:\n                if temp is headB:\n                    return temp\n                temp = temp.next\n                headB = headB.next\n        elif lenB &gt; lenA:\n            temp = headB\n            # Move pointer of longer list forward by difference\n            while diff &gt; 0:\n                temp = temp.next\n                diff -= 1\n            # Walk both pointers together until they meet\n            while temp:\n                if temp is headA:\n                    return temp\n                temp = temp.next\n                headA = headA.next\n        else:\n            # Both lists have same length, start from beginning\n            temp = headA\n            while temp:\n                if temp is headB:\n                    return temp\n                temp = temp.next\n                headB = headB.next\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">getIntersectionNode<\/span><span style=\"color: #D4D4D4\">(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">headA<\/span><span style=\"color: #D4D4D4\">: ListNode, <\/span><span style=\"color: #9CDCFE\">headB<\/span><span style=\"color: #D4D4D4\">: ListNode<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    ) -&gt; Optional[ListNode]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lenA = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lenB = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lastNodeofA = <\/span><span style=\"color: #569CD6\">None<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lastNodeofB = <\/span><span style=\"color: #569CD6\">None<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = headA<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Calculate length of list A and find its last node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            lenA += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp.next <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                lastNodeofA = temp  <\/span><span style=\"color: #6A9955\"># Store last node of A<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = headB<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Calculate length of list B and find its last node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            lenB += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp.next <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                lastNodeofB = temp  <\/span><span style=\"color: #6A9955\"># Store last node of B<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># If last nodes are different, no intersection exists<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> lastNodeofA <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> lastNodeofB:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        diff = <\/span><span style=\"color: #DCDCAA\">abs<\/span><span style=\"color: #D4D4D4\">(lenA - lenB)  <\/span><span style=\"color: #6A9955\"># Calculate difference in lengths<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Align starting points based on which list is longer<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> lenA &gt; lenB:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = headA<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Move pointer of longer list forward by difference<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> diff &gt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                diff -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Walk both pointers together until they meet<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> headB:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> temp<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                headB = headB.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">elif<\/span><span style=\"color: #D4D4D4\"> lenB &gt; lenA:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = headB<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Move pointer of longer list forward by difference<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> diff &gt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                diff -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Walk both pointers together until they meet<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> headA:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> temp<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                headA = headA.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Both lists have same length, start from beginning<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = headA<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> headB:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> temp<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                headB = headB.next<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution works in multiple phases. First, we calculate the length of both lists while also storing their last nodes. By comparing the last nodes, we can quickly determine if the lists intersect at all &#8211; if they don&#8217;t share the same last node, they can&#8217;t intersect. If they do intersect, we calculate the difference in lengths and move the pointer of the longer list forward by that difference. This aligns both pointers so they have the same distance remaining to the intersection. Finally, we move both pointers together until they meet.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>List A:&nbsp;<code>1 -&gt; 2 -&gt; 8 -&gt; 4 -&gt; 5<\/code>&nbsp;(length = 5)<\/li>\n\n\n\n<li>List B:&nbsp;<code>3 -&gt; 6 -&gt; 8 -&gt; 4 -&gt; 5<\/code>&nbsp;(length = 5)<\/li>\n<\/ul>\n\n\n\n<p><strong>Calculate Lengths:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>lenA = 5, lastNodeofA = node 5<\/li>\n\n\n\n<li>lenB = 5, lastNodeofB = node 5<\/li>\n\n\n\n<li>Same last node, so intersection exists<\/li>\n<\/ul>\n\n\n\n<p><strong>Align Starting Points:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>diff = |5 &#8211; 5| = 0<\/li>\n\n\n\n<li>Both lists have same length, no alignment needed<\/li>\n<\/ul>\n\n\n\n<p><strong>Walk Together:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Compare node 1 and node 3: different, continue<\/li>\n\n\n\n<li>Compare node 2 and node 6: different, continue<\/li>\n\n\n\n<li>Compare node 8 and node 8: same! Return node 8<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;Intersection at node 8<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(m + n) &#8211; We traverse each list a few times but still linear<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(1) &#8211; We only use a few variables<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like two runners on a track where one starts ahead. We calculate how far ahead one is, then give the other runner a head start so they both have the same distance remaining. When they start running together, they&#8217;ll meet at the finish line (intersection point).<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-solution-3-optimal-approach-two-pointers-with-list-switching\">Solution 3: Optimal Approach (Two Pointers with List Switching)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-intuition\">Intuition<\/h3>\n\n\n\n<p>Here&#8217;s a brilliant trick! Imagine two friends trying to meet, but they&#8217;re on different paths of different lengths. Instead of calculating distances, they agree on this rule: &#8220;When I reach the end of my path, I&#8217;ll start walking on your path from the beginning.&#8221; If their paths intersect, they&#8217;ll definitely meet at the intersection point because they&#8217;ll both have walked the same total distance!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"18-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Set Up Two Pointers<\/strong>: Start both pointers at the heads of their respective lists<\/li>\n\n\n\n<li><strong>Walk and Switch<\/strong>: When a pointer reaches the end of its list, redirect it to the head of the other list<\/li>\n\n\n\n<li><strong>Keep Moving<\/strong>: Both pointers will eventually walk the same total distance<\/li>\n\n\n\n<li><strong>Meet at Intersection<\/strong>: If the lists intersect, the pointers will meet at the intersection node<\/li>\n\n\n\n<li><strong>No Intersection<\/strong>: If lists don&#8217;t intersect, both pointers will become null at the same time<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"19-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def getIntersectionNode(\n        self, headA: ListNode, headB: ListNode\n    ) -&gt; Optional[ListNode]:\n        if not headA or not headB:\n            return None  # If either list is empty, no intersection possible\n\n        temp1, temp2 = headA, headB  # Two pointers starting at respective heads\n\n        # Keep moving until both pointers meet\n        while temp1 != temp2:\n            if temp1 is not None:\n                temp1 = temp1.next      # Move to next node in current list\n            else:\n                temp1 = headB           # Switch to other list when current ends\n            \n            if temp2 is not None:\n                temp2 = temp2.next      # Move to next node in current list\n            else:\n                temp2 = headA           # Switch to other list when current ends\n\n        return temp1  # Return intersection node (or None if no intersection)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">getIntersectionNode<\/span><span style=\"color: #D4D4D4\">(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">headA<\/span><span style=\"color: #D4D4D4\">: ListNode, <\/span><span style=\"color: #9CDCFE\">headB<\/span><span style=\"color: #D4D4D4\">: ListNode<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    ) -&gt; Optional[ListNode]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> headA <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> headB:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># If either list is empty, no intersection possible<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp1, temp2 = headA, headB  <\/span><span style=\"color: #6A9955\"># Two pointers starting at respective heads<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Keep moving until both pointers meet<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp1 != temp2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp1 <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp1 = temp1.next      <\/span><span style=\"color: #6A9955\"># Move to next node in current list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp1 = headB           <\/span><span style=\"color: #6A9955\"># Switch to other list when current ends<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp2 <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp2 = temp2.next      <\/span><span style=\"color: #6A9955\"># Move to next node in current list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                temp2 = headA           <\/span><span style=\"color: #6A9955\"># Switch to other list when current ends<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> temp1  <\/span><span style=\"color: #6A9955\"># Return intersection node (or None if no intersection)<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"20-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This elegant solution uses two pointers that traverse both lists in a special way. Each pointer walks through its own list first, and when it reaches the end, it switches to the other list. This ensures both pointers walk the same total distance: length of list A + length of list B. If the lists intersect, the pointers will meet at the intersection point. If they don&#8217;t intersect, both pointers will become null simultaneously, and the loop will end.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"21-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>List A:&nbsp;<code>1 -&gt; 2 -&gt; 8 -&gt; 4 -&gt; 5<\/code>&nbsp;(length = 5)<\/li>\n\n\n\n<li>List B:&nbsp;<code>3 -&gt; 6 -&gt; 8 -&gt; 4 -&gt; 5<\/code>&nbsp;(length = 5)<\/li>\n<\/ul>\n\n\n\n<p><strong>Step-by-step traversal:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>temp1=1, temp2=3: different, continue<\/li>\n\n\n\n<li>temp1=2, temp2=6: different, continue<\/li>\n\n\n\n<li>temp1=8, temp2=8: same! Return node 8<\/li>\n<\/ul>\n\n\n\n<p>Actually, let me trace a more interesting example:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>List A:&nbsp;<code>4 -&gt; 1 -&gt; 8 -&gt; 4 -&gt; 5<\/code>&nbsp;(length = 5)<\/li>\n\n\n\n<li>List B:&nbsp;<code>5 -&gt; 6 -&gt; 1 -&gt; 8 -&gt; 4 -&gt; 5<\/code>&nbsp;(length = 6, intersects at node with value 8)<\/li>\n<\/ul>\n\n\n\n<p><strong>Traversal:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initially: temp1 at 4 (A), temp2 at 5 (B)<\/li>\n\n\n\n<li>After a few steps: temp1 finishes A, switches to B; temp2 continues in B<\/li>\n\n\n\n<li>Later: temp2 finishes B, switches to A; temp1 continues in B<\/li>\n\n\n\n<li>Eventually: Both pointers meet at the intersection node<\/li>\n<\/ul>\n\n\n\n<p><strong>Key insight:<\/strong>&nbsp;temp1 travels A_length + B_length, temp2 travels B_length + A_length. Same total distance!<\/p>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;Intersection found at the common node<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"22-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(m + n) &#8211; Each pointer traverses at most both lists once<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(1) &#8211; We only use two pointer variables<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"23-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like two people agreeing to walk each other&#8217;s routes. Person A walks route A then route B, while Person B walks route B then route A. Since they walk the same total distance, if their routes intersect, they&#8217;ll meet at the intersection point. It&#8217;s a beautiful mathematical solution that requires no extra calculations!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"24-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force (Set)<\/td><td>O(m + n)<\/td><td>O(m)<\/td><td>Easy<\/td><td>Learning the concept<\/td><\/tr><tr><td>Better (Length + Alignment)<\/td><td>O(m + n)<\/td><td>O(1)<\/td><td>Medium<\/td><td>Understanding the logic<\/td><\/tr><tr><td>Optimal (Two Pointers)<\/td><td>O(m + n)<\/td><td>O(1)<\/td><td>Hard<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>optimal approach<\/strong>&nbsp;is generally preferred because it&#8217;s the most elegant and uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you&#8217;re first learning about intersection problems.<\/p>\n\n\n\n<p>All three solutions effectively solve the problem with the same time complexity, but the optimal solution is the most beautiful because it leverages a mathematical insight: if two people walk the same total distance on intersecting paths, they&#8217;ll meet at the intersection. This technique is widely applicable and demonstrates the power of clever pointer manipulation in linked list problems!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given the heads of two singly linked-lists&nbsp;headA&nbsp;and&nbsp;headB, return&nbsp;the node at which the two lists intersect. If the two linked lists have no intersection at all, return&nbsp;null. Here&#8217;s the [Problem Link] to begin with. For example, the following two linked lists begin to intersect at node&nbsp;c1: The test cases are generated such that there are no<\/p>\n","protected":false},"author":1,"featured_media":671,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[18,29],"class_list":{"0":"post-670","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-hard","10":"tag-singly-linked-list"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/intersection-of-two-linked-lists-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/670","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=670"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/670\/revisions"}],"predecessor-version":[{"id":675,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/670\/revisions\/675"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/671"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=670"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=670"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=670"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}