求链表交点

package program

import (
    "fmt"
    "testing"
)

type ListNode struct {
    Val  int
    Next *ListNode
}

func TestLinkRepeatNode(t *testing.T) {
    node8 := &ListNode{Val: 8, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}
    //构造链表A
    headA := &ListNode{Val: 4, Next: &ListNode{Val: 1, Next: node8}}
    headB := &ListNode{Val: 5, Next: &ListNode{Val: 0, Next: &ListNode{Val: 1, Next: node8}}}
    fmt.Println(getIntersectionNode(headA, headB))
}
func getLength(node *ListNode) int {
    length := 0
    for node != nil {
        length++
        node = node.Next
    }
    return length
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    //先计算出链表A的长度
    lengthA := getLength(headA)
    lengthB := getLength(headB)
    //让指针B先走lengthB - lengthA步
    for i := 0; i < lengthB-lengthA; i++ {
        headB = headB.Next
    }
    for headA != headB {
        headA = headA.Next
        headB = headB.Next
    }
    return headA
}