NUHMAN.com

Introduction

LeetCode 160 asks us to find the node at which two singly linked lists intersect. If the two linked lists do not intersect, return null. The challenge lies in solving this problem efficiently without extra space, meaning we should aim for a solution that works in O(n) time and O(1) space.

Problem Statement

Given the heads of two singly linked lists headA and headB, the task is to find the node at which they intersect. If they do not intersect, return null.

Function Signature:

go

func getIntersectionNode(headA, headB *ListNode) *ListNode

• Input:
• Two linked lists headA and headB, each representing the head node of a singly linked list.
• Output:
• Return the node at which the two linked lists intersect, or null if there is no intersection.

Approach

Key Idea:

The key observation here is that if two linked lists intersect, they will share the same memory addresses starting from the point of intersection. We can utilize this fact to detect the intersection without needing extra space.

We will use two pointers, one for each linked list. By traversing the lists in a clever way, we can make the two pointers meet at the intersection node, if one exists.

Steps:

1. Pointer Traversal:

• We initialize two pointers, pA for headA and pB for headB.

1. Traverse the Lists:

• We traverse both lists by moving pA and pB forward.
• When pA reaches the end of headA, we redirect it to headB. Similarly, when pB reaches the end of headB, we redirect it to headA.

1. Why This Works:

• If the lists intersect, the two pointers will eventually meet at the intersection node after at most 2n steps (where n is the number of nodes in the list). This is because both pointers will traverse equal lengths even if they start at different points.

1. No Intersection:

• If there is no intersection, both pointers will eventually traverse both lists completely and meet at null.

Time Complexity:

• O(n + m), where n and m are the lengths of headA and headB, respectively. Each pointer traverses both lists at most once.

Space Complexity:

• O(1) because we only use two pointers and no extra data structures.

Go Implementation

go

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // If either of the lists is empty, return nil
    if headA == nil || headB == nil {
        return nil
    }

    // Initialize two pointers for both linked lists
    pA, pB := headA, headB

    // Traverse both lists, redirecting when reaching the end
    // When both pointers reach the end, they will be redirected to the other list
    // If they meet, it's the intersection point
    // If not, they will both reach the end and be null at the same time
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }

        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }

    // Return the intersection node (or nil if no intersection)
    return pA
}

Explanation of the Code:

1. Pointer Initialization:

• We initialize two pointers, pA and pB, starting from headA and headB respectively.

2. Traverse the Lists:

• The loop continues until the pointers pA and pB meet. Inside the loop:
• If pA reaches the end of headA, we redirect it to headB. Similarly, if pB reaches the end of headB, we redirect it to headA.
• This ensures that the pointers traverse both lists and eventually meet at the intersection (if one exists) or both become null.

3. Return the Intersection:

• If the lists intersect, the pointers will meet at the intersection node, and we return that node.
• If they don't intersect, the pointers will eventually both become null and we return null.

4. Time and Space Complexity:

OperationComplexityTraversalO(n + m)Space ComplexityO(1)OverallO(n + m)

• Time Complexity: The time complexity is O(n + m) because each pointer traverses each list at most once.
• Space Complexity: The space complexity is O(1) because we are only using two pointers to traverse the lists.

Example

Example 1:

go

// Example of intersecting lists

headA := &ListNode{Val: 4}
headA.Next = &ListNode{Val: 1}
intersectNode := &ListNode{Val: 8}
headA.Next.Next = intersectNode
intersectNode.Next = &ListNode{Val: 4}
intersectNode.Next.Next = &ListNode{Val: 5}

headB := &ListNode{Val: 5}
headB.Next = &ListNode{Val: 0}
headB.Next.Next = &ListNode{Val: 1}
headB.Next.Next.Next = intersectNode

result := getIntersectionNode(headA, headB)
fmt.Println(result.Val) // Output: 8

Explanation:

• The two lists intersect at the node with value 8, so the result is the node with value 8.

Example 2:

go

// Example of non-intersecting lists

headA := &ListNode{Val: 1}
headA.Next = &ListNode{Val: 2}
headB := &ListNode{Val: 3}
headB.Next = &ListNode{Val: 4}

result := getIntersectionNode(headA, headB)
fmt.Println(result) // Output: nil

Explanation:

• The two lists do not intersect, so the result is nil.

Conclusion

LeetCode 160 provides a classic problem of finding the intersection of two linked lists. By using the two-pointer technique with the sliding window approach, we can solve the problem efficiently in O(n + m) time with O(1) space, where n and m are the lengths of the two lists. This method ensures that we don't need extra space for a hashset or other data structures, making it an optimal solution.