Intersection of Two Linked Lists easy

Problem Statement

Write a function to find the intersection of two singly linked lists. The intersection is defined as the node at which the two lists begin to intersect (if one exists). If there is no intersection, return null.

Example 1

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output: Intersecting node's reference: 8

Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). 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.

Example 2

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output: Intersecting node's reference: 2

Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). 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.

Steps

1. Find the lengths of both linked lists: Iterate through each list and count the number of nodes.
2. Find the difference in lengths: Calculate the absolute difference between the lengths of the two lists.
3. Advance the longer list: Move the pointer of the longer list forward by the difference in lengths calculated in step 2. This ensures both pointers are at the same distance from the potential intersection point (if one exists).
4. Iterate simultaneously: Iterate through both lists simultaneously, comparing nodes at each step. If the nodes are the same, that's the intersection point. If you reach the end of either list without finding a match, there is no intersection.

Explanation

The key idea behind this solution is to equalize the lengths of the linked lists before comparing them. If the lists intersect, they will share a common tail. By advancing the longer list to match the shorter list's length before iterating simultaneously, we guarantee that if an intersection exists, both pointers will reach it at the same time.

Code

using System;

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

public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        // Get lengths of lists
        int lenA = GetLength(headA);
        int lenB = GetLength(headB);

        // Adjust pointers to start at the same distance from the potential intersection
        ListNode pA = headA;
        ListNode pB = headB;
        if (lenA > lenB) {
            int diff = lenA - lenB;
            for (int i = 0; i < diff; i++) {
                pA = pA.next;
            }
        } else {
            int diff = lenB - lenA;
            for (int i = 0; i < diff; i++) {
                pB = pB.next;
            }
        }

        // Iterate simultaneously to find intersection
        while (pA != null && pB != null) {
            if (pA == pB) return pA;
            pA = pA.next;
            pB = pB.next;
        }

        return null; // No intersection found
    }

    // Helper function to get length of linked list
    private int GetLength(ListNode head) {
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

Complexity

• Time Complexity: O(m + n), where m and n are the lengths of the two linked lists. We traverse each list once.
• Space Complexity: O(1). We use only a constant amount of extra space.