160. Intersection of Two Linked Lists

 

Finding the Intersection Node in Two Linked Lists with JavaScript

Finding the intersection node between two singly-linked lists is a classic problem that can be efficiently solved with a bit of clever maneuvering. In this blog post, we'll walk through the intuition, approach, and complexity analysis of finding the intersection node using JavaScript. We'll also include the complete code and a link to my detailed solution on LeetCode.

Intuition

The essence of solving this problem lies in the fact that the intersection point, if it exists, will be at the same distance from the end of both lists once they are aligned correctly. By calculating the lengths of both lists and aligning their starting points, we can simultaneously traverse the lists to find the intersection node.

Approach

  1. Calculate the Lengths of Both Lists:

    • First, we traverse both linked lists to determine their lengths. This helps in identifying the longer list and the difference in lengths between the two lists.

  2. Align the Starting Points:

    • Reset the pointers to the head of each list.

    • Advance the pointer of the longer list by the difference in lengths to align both lists for simultaneous traversal.

  3. Find the Intersection:

    • Traverse both lists simultaneously. If the nodes at the current positions are the same, we have found the intersection node.

    • If the nodes are different, continue moving both pointers one step at a time until they either meet or reach the end of the lists.

Code

Here is the complete JavaScript code to find the intersection node in two singly-linked lists:

javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let tempA = headA;
    let tempB = headB;
    // Calculate length
    let lengthA = 0;
    let lengthB = 0;
    while(tempA) {
        lengthA++;
        tempA = tempA.next;
    }
    while(tempB) {
        lengthB++;
        tempB = tempB.next;
    }
    // Move towards lengthA - lengthB
    tempA = headA;
    tempB = headB;
    if(lengthA > lengthB) {
        for(let i = 0; i < lengthA - lengthB; i++) {
            tempA = tempA.next;
        }
    } else {
        for(let i = 0; i < lengthB - lengthA; i++) {
            tempB = tempB.next;
        }
    }
    // Now check for intersection
    while(tempA != tempB) {
        tempA = tempA.next;
        tempB = tempB.next;
    }
    return tempA;
};

Complexity

  • Time Complexity:

    • Calculating the lengths of the two lists takes O(m + n) time, where m is the length of list A and n is the length of list B.

    • Aligning the starting points takes O(abs(m - n)) time.

    • Traversing both lists to find the intersection node takes O(min(m, n)) time.

    • Therefore, the overall time complexity is O(m + n).

  • Space Complexity:

    • The space complexity is O(1) as we only use a constant amount of extra space for pointers and counters.

Conclusion

This method provides an efficient and straightforward solution to finding the intersection node of two singly-linked lists. By aligning the lists and traversing them simultaneously, we can identify the intersection point with minimal extra space.

For more detailed explanations and additional solutions, check out my solution on LeetCode: Intersection of Two Linked Lists - LeetCode

I hope this guide helps you understand how to solve the intersection node problem using JavaScript. Happy coding! šŸš€

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more