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

44 lines
750 B
Go
Raw Permalink Normal View History

2022-06-06 18:51:38 +00:00
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
}