Leetcode专题[链表]-面试题 02.07-链表相交

力扣链接：
https://leetcode-cn.com/probl...
解题思路：

1. 首先还是之前的结论，在拿到题目的时候，要先找寻规律，从题干中找出有用的信息，这道题题干中请你找出并返回两个单链表相交的起始节点，这里说明如果有相交的节点，那么在这个节点之后两个链表是完全相同的，也就是说，从某个节点开始，相对较短的节点跟相对较长的节点是末端对齐的
2. 如果没有相交的节点，那就返回nil
3. 所以这道题的解法就是：先将两个链表的末端对齐，对齐的办法就是较长的链表先走两个链表的差值步，然后两个链表同时开始走，查找是否有相同的节点，知道找到/结束
4. 双指针：快指针指向较长的链表对齐后的节点，慢指针是较短链表的起点

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 本质上还是快慢指针的思想
// 先把两个链表尾部对齐
// 然后同时开始遍历
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    curA, curB := headA, headB
    lenA, lenB := 0, 0
    // 求链表A的长度
    for curA != nil {
        curA = curA.Next
        lenA++
    }
    // 求链表B的长度
    for curB != nil {
        curB = curB.Next
        lenB++
    }
    // 求A和B的差值
    diffLen := diffLen(lenA, lenB)
    var fast, slow *ListNode
    // 长度更长的先走difflen步
    if lenA > lenB {
        fast = headA
        slow = headB
    } else {
        fast = headB
        slow = headA
    }
    for i := 0; i < diffLen; i++ {
            fast = fast.Next
    }
    // 同时开始走
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

func diffLen(a, b int) int {
    if a > b {
        return a - b
    }
    return b - a
}