Intersection of Two Linked Lists

1. Problem Description

Write a program that finds the first node at which two singly linked lists intersect.

2. Approach

1. Approach 1
   • An intersection means all nodes after the intersection node are shared by both lists
   • Advance the longer list by the length difference, then move both pointers together until they reach the same node

3. Implementation

3.1. Length Difference

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA := 0
    currentA := headA
    for currentA != nil {
        lenA++
        currentA = currentA.Next
    }

    lenB := 0
    currentB := headB
    for currentB != nil {
        lenB++
        currentB = currentB.Next
    }

    currentA = headA
    currentB = headB
    if lenA > lenB {
        diff := lenA - lenB
        for i := 0; i < diff; i++ {
            currentA = currentA.Next
        }
    }else {
        diff := lenB - lenA
        for i := 0; i < diff; i++ {
            currentB = currentB.Next
        }
    }

    for currentB != currentA {
        currentA = currentA.Next
        currentB = currentB.Next
    }

    return currentB
}

4. References

• 160. Intersection of Two Linked Lists - LeetCode