leet-code/intersection-of-two-linked-lists/sol_O(1)_mem.go

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

// O(n + m) time and O(1) memory solution
// Gets the length of each list, then
// lines them up and searches for equal
// nodes.
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	len1, len2 := getLen(headA), getLen(headB)
	diff := len1 - len2
	for diff > 0 {
		headA = headA.Next
		diff--
	}
	for diff < 0 {
		headB = headB.Next
		diff++
	}
	for headA != headB {
		headA = headA.Next
		headB = headB.Next
	}
	return headA
}

func getLen(head *ListNode) int {
	len := 0
	for current := head; current != nil; current = current.Next {
		len++
	}
	return len
}