What is the time complexity of Intersection of Two Linked Lists?

The optimal solution has a time complexity of O(m+n).

What data structures are used to solve Intersection of Two Linked Lists?

This problem uses Hash Table, Linked List, Two Pointers. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Intersection of Two Linked Lists?

Insight 1: The key observation is that if we traverse both lists simultaneously, one pointer moving one step at a time, if there's an intersection, the pointers will eventually meet at the intersection point. If there's no intersection, the pointers will reach the end of both lists simultaneously (becoming `null`). Insight 2: The Two Pointers approach is perfectly suited here. It cleverly avoids the need for extra space (like a hash table) by cleverly manipulating the traversal of the two lists.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Intersection of Two Linked Lists - LeetCode 160 Solution

Q: Which companies ask LeetCode 160. Intersection of Two Linked Lists in interviews?

This problem is frequently asked at Accenture, Airbnb, Goldman Sachs, Nvidia, Oracle and 2 more companies.

Intersection of Two Linked Lists - Complete Solution Guide

Intersection of Two Linked Lists is LeetCode problem 160, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given the heads of two singly linked-lists headA and headB , return the node at which the two lists intersect . If the two linked lists have no intersection at all, return null . For example, the following two linked lists begin to intersect at node c1 : The test cases are generated such that there are no cycles anywhere in the entire linked structure. Note that the linked lists must retain their original structure after the function returns. Custom Judge: The inputs to the judge are given as fo

Detailed Explanation

The problem asks to find the node at which two singly linked lists intersect. The input consists of the heads of two linked lists, `headA` and `headB`. The output is the intersecting node (if it exists); otherwise, it's `null` (or equivalent in the respective language). The lists might intersect at any point, or not at all. Importantly, the lists' structure must remain unchanged after the function execution. The problem also provides example inputs and outputs to illustrate the concept of intersection, highlighting that the same numerical value doesn't automatically mean intersection; it's about the memory addresses of the nodes.

Solution Approach

The solution uses a two-pointer approach. Two pointers, `a_pointer` and `b_pointer`, are initialized to point to the heads of `headA` and `headB`, respectively. The pointers traverse the lists simultaneously. If `a_pointer` reaches the end of list A (`a_pointer is None`), it's reset to `headB`; similarly, `b_pointer` is reset to `headA` if it reaches the end of list B. This process continues until the two pointers meet. If they meet at a node, that's the intersection node; if they both reach the ends (become `null` simultaneously), there is no intersection.

Step-by-Step Algorithm

Step 1: Initialize two pointers, `a_pointer` to `headA` and `b_pointer` to `headB`. Check if either head is null. If so, return null.
Step 2: Enter a `while` loop that continues as long as `a_pointer` and `b_pointer` are not equal.
Step 3: Inside the loop: If `a_pointer` is `null`, set it to `headB`; otherwise, move `a_pointer` to its next node (`a_pointer.next`).
Step 4: Similarly, if `b_pointer` is `null`, set it to `headA`; otherwise, move `b_pointer` to its next node (`b_pointer.next`).
Step 5: After the loop, `a_pointer` (and `b_pointer`) will point to the intersection node (or `null` if there's no intersection). Return `a_pointer`.

Key Insights

Insight 1: The key observation is that if we traverse both lists simultaneously, one pointer moving one step at a time, if there's an intersection, the pointers will eventually meet at the intersection point. If there's no intersection, the pointers will reach the end of both lists simultaneously (becoming `null`).
Insight 2: The Two Pointers approach is perfectly suited here. It cleverly avoids the need for extra space (like a hash table) by cleverly manipulating the traversal of the two lists.
Insight 3: Handling `null` pointers is crucial. The code must gracefully handle cases where one or both lists are empty, or the intersection is at the end of one of the lists.

Complexity Analysis

Time Complexity: O(m+n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, Linked List, Two Pointers.

Companies

Asked at: Accenture, Airbnb, Goldman Sachs, Nvidia, Oracle, TikTok, VMware.

Intersection of Two Linked Lists | LeetCode 160

Easy

Hash Table Linked List Two Pointers

Time: O(m+n)Space: O(1)

Solution Code

Available in:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }

        return a;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 160: Intersection of Two Linked Lists - Detailed explanation and solution approaches.

Topics

Hash Table Linked List Two Pointers

Companies

AccentureAirbnbGoldman SachsNvidiaOracleTikTokVMware

Stats

Difficulty:Easy

Languages:4

Companies:7

Problem #:160

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize two pointers, `a_pointer` to `headA` and `b_pointer` to `headB`. Check if either head is null. If so, return null.
2
Step 2: Enter a `while` loop that continues as long as `a_pointer` and `b_pointer` are not equal.
3
Step 3: Inside the loop: If `a_pointer` is `null`, set it to `headB`; otherwise, move `a_pointer` to its next node (`a_pointer.next`).
4
Step 4: Similarly, if `b_pointer` is `null`, set it to `headA`; otherwise, move `b_pointer` to its next node (`b_pointer.next`).
5
Step 5: After the loop, `a_pointer` (and `b_pointer`) will point to the intersection node (or `null` if there's no intersection). Return `a_pointer`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m+n)

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm traverses each list at most once. In the worst case (no intersection), it iterates through list A and list B completely. Therefore, the time complexity is linear, proportional to the sum of the lengths of the two lists (m + n). The space complexity is constant because only a fixed number of variables (two pointers) are used, regardless of the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Hash Table Approach

Iterate through one list (e.g., list A), storing each node's address in a hash table. Then, iterate through list B, checking if each node's address is present in the hash table. If a match is found, that's the intersection node.

Time: O(m + n)Space: O(m) or O(n) (depending on which list is stored in the hash table)

Trade-offs: This approach has the same time complexity but higher space complexity compared to the two-pointer approach. It's less efficient in terms of memory usage, especially for very large lists. The two-pointer approach is generally preferred due to its O(1) space complexity.

✨

Key Insights

1Insight 1: The key observation is that if we traverse both lists simultaneously, one pointer moving one step at a time, if there's an intersection, the pointers will eventually meet at the intersection point. If there's no intersection, the pointers will reach the end of both lists simultaneously (becoming `null`).
2Insight 2: The Two Pointers approach is perfectly suited here. It cleverly avoids the need for extra space (like a hash table) by cleverly manipulating the traversal of the two lists.
3Insight 3: Handling `null` pointers is crucial. The code must gracefully handle cases where one or both lists are empty, or the intersection is at the end of one of the lists.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: Empty lists: The code correctly handles cases where either `headA` or `headB` (or both) are `null` by returning `null` immediately.
Edge case 2: Intersection at the end of one list: The pointer resetting mechanism correctly identifies the intersection even if it occurs at the tail of one of the lists.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle `null` pointers: Not properly checking for `null` values at the beginning and during list traversal leads to `NullPointerExceptions` or segmentation faults.

✗Common mistake 2: Incorrect pointer resetting: Not correctly handling the case where one pointer reaches the end and needs to be reset to the head of the other list leads to an infinite loop or incorrect results.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting cycles in linked lists: A modified version of this two-pointer approach (Floyd's cycle-finding algorithm) is used to detect cycles efficiently in linked lists.

🏦Real-world scenario 2: Data structure merging or reconciliation: In scenarios where two data streams are represented as linked lists, this algorithm can be useful to find common elements or detect conflicts.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

👨‍💻 From Experience

This is one of the first problems I solved when learning Hash Table. It's a great foundation for more complex problems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Intersection of Two Linked Lists"?

For this easy-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether linked list techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?