algoadvance

Leetcode 160. Intersection of Two Linked Lists

Problem Statement

The problem is to determine the node at which two singly linked lists intersect. If the two linked lists have no intersection at all, return null.

Definition for singly-linked list:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

Given heads for two singly linked lists headA and headB, return the node at which the two lists intersect. If there is no intersection, return null.

Example:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must be the same node, not two nodes with the same value).

Clarifying Questions

  1. Q: What can we assume about the input linked lists? A: You can assume the lists are non-cyclical and may have different lengths.

  2. Q: What should we return if there is no intersection? A: Return null.

Strategy

To solve this problem, we can use the following approach:

  1. Get the lengths of both linked lists.
  2. Align the start of the longer list such that both lists are equidistant from the end.
  3. Traverse both lists simultaneously until a common node is found or the end of lists is reached.

This method works because once both lists are aligned at the same starting point relative to their ends, any intersection will be detected as both lists are traversed together.

Steps:

  1. Calculate the lengths of both linked lists.
  2. Adjust the starting point of the longer list by moving its head forward by the difference in lengths.
  3. Traverse both lists together until a node match is found or the end is reached.

Code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        // Get the length of both lists
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);
        
        // Align heads
        if (lengthA > lengthB) {
            headA = moveForward(headA, lengthA - lengthB);
        } else if (lengthB > lengthA) {
            headB = moveForward(headB, lengthB - lengthA);
        }
        
        // Traverse both lists and find the intersection
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
    
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
    
    private ListNode moveForward(ListNode head, int steps) {
        while (steps > 0 && head != null) {
            head = head.next;
            steps--;
        }
        return head;
    }
}

Time Complexity

This solution effectively adjusts the starts of the lists to ensure any intersection is found efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI