160. 相交链表 #
题目地址 #
解题思路 #
如果两个链表相交，那么相交点之后的长度是相同的。
所以，我们需要做的事情是，让两个链表从距离末尾同等距离的位置开始遍历。而这个位置只能是较短链表的头结点位置。为此，需要求出两个链表的长度并消除两个链表的长度差。
具体实现 #
```go
package main
import "fmt"
type ListNode struct {
Next *ListNode
Val int
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
var (
currA, currB = headA, headB
lenA, lenB int
)
// 计算链表的长度
for currA != nil {
lenA++
currA = currA.Next
}
for currB != nil {
lenB++
currB = currB.Next
}
currA, currB = headA, headB
// 判断谁是最长的,把最长的赋值给 currA
gap := 0
if lenA >= lenB {
gap = lenA - lenB
} else {
gap = lenB - lenA
currA, currB = currB, currA
}
for gap > 0 { // 移动最大的位置
currA = currA.Next
gap--
}
// 同时移动
for currA != nil {
if currA == currB {
return currA // 这里 return currB 也行
}
currA = currA.Next
currB = currB.Next
}
return nil
}
func main() {
t := &ListNode{
Next: &ListNode{
Next: nil,
Val: 9,
},
Val: 8,
}
ca := &ListNode{
Next: &ListNode{
Next: t,
Val: 2,
},
Val: 1,
}
cb := &ListNode{
Next: &ListNode{
Next: &ListNode{
Next: t,
Val: 5,
},
Val: 4,
},
Val: 3,
}
ret := getIntersectionNode(ca, cb)
fmt.Println(ret)
}
```