leetcode0207 链表相交

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

示例

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解析

这道题可以先画图（结合前几道，发现链表的题目画图都可以帮助梳理思路，不要全凭脑子想，一定要动动手画一下）
这里还有一个数学技巧，可以先设第一个链表的长度为A，第二个链表长度为B，然后设第一个链表交点前的长度为C，第二个的为D，则有：
A - C = B - D 因为后面是相交的部分，换算一下就有
A + D = B + C 这就说明了走完全程后，再走一边另一个链表的前半部分，最后的交点就是一样的。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    a := headA
    b := headB
    for  (a != b) {
        if a != nil {
            a = a.Next
        } else {
            a = headB
        }
        if b != nil {
            b = b.Next
        } else {
            b = headA
        }
    }
    return a
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

注意go中没有三元表达式，不然会简洁很多