相交链表

1. 题目描述

编写一个程序，找到两个单链表相交的起始节点。

2. 思路

1. 思路一
   • 相交意味着相交节点之后的节点是重合的
   • 先让长链表走差值步，然后一起走到相同的节点

3. 实现

3.1. 差值

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA := 0
    currentA := headA
    for currentA != nil {
        lenA++
        currentA = currentA.Next
    }

    lenB := 0
    currentB := headB
    for currentB != nil {
        lenB++
        currentB = currentB.Next
    }

    currentA = headA
    currentB = headB
    if lenA > lenB {
        diff := lenA - lenB
        for i := 0; i < diff; i++ {
            currentA = currentA.Next
        }
    }else {
        diff := lenB - lenA
        for i := 0; i < diff; i++ {
            currentB = currentB.Next
        }
    }

    for currentB != currentA {
        currentA = currentA.Next
        currentB = currentB.Next
    }

    return currentB
}

4. 参考

• 160. 相交链表 - 力扣（LeetCode）