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 {
    lengthA := getLength(headA)
    lengthB := getLength(headB)
    if lengthA > lengthB {
        headA = runNSteps(headA, lengthA-lengthB)
    }else {
        headB = runNSteps(headB, lengthB-lengthA)
    }
    for headA != nil {
        if headA == headB {
            return headA
        }
        headA=headA.Next
        headB=headB.Next
    }
    return nil
}

func runNSteps(h *ListNode, n int) *ListNode {
    for i :=0 ;i < n;i++ {
        h = h.Next
    }
    return h
}

func getLength(head *ListNode) int {
    var length int
    for head != nil {
        length++
        head = head.Next
    }
    return length
}

4. References

• 160. Intersection of Two Linked Lists - LeetCode