1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39// https://leetcode.com/problems/intersection-of-two-linked-lists/
package intersectionoftwolinkedlists
import "github.com/jtr109/lcutils/listnode"
type ListNode = listnode.ListNode
// time complexity: O(N)
// space complexity: O(1)
func getIntersectionNode(headA, headB *ListNode) *ListNode {
lengthA := lengthListNode(headA)
lengthB := lengthListNode(headB)
if lengthA > lengthB {
for i := 0; i < lengthA-lengthB; i++ {
headA = headA.Next
}
} else {
for i := 0; i < lengthB-lengthA; i++ {
headB = headB.Next
}
}
for headA != headB {
headA = headA.Next
headB = headB.Next
}
return headA
}
func lengthListNode(head *ListNode) int {
length := 0
current := head
for current != nil {
length++
current = current.Next
}
return length
}