44 lines
750 B
Go
44 lines
750 B
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
|
||
|
|
}
|