相交链表

1. 题目描述

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

2. 思路

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

3. 实现

3.1. 差值

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lengthA := getLength(headA)
    lengthB := getLength(headB)
    if lengthA > lengthB {
        headA = runNSteps(headA, lengthA-lengthB)
    }else {
        headB = runNSteps(headB, lengthB-lengthA)
    }
    for headA != nil {
        if headA == headB {
            return headA
        }
        headA=headA.Next
        headB=headB.Next
    }
    return nil
}

func runNSteps(h *ListNode, n int) *ListNode {
    for i :=0 ;i < n;i++ {
        h = h.Next
    }
    return h
}

func getLength(head *ListNode) int {
    var length int
    for head != nil {
        length++
        head = head.Next
    }
    return length
}

4. 参考

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