找出两个链表交点（golang 版）

// main.gopackage intertwolink
// 输入两个链表，返回相交节点指针，无交点则返回nil// 时间复杂度：O(m+n)  m和n分别表示两链表长度// 空间复杂度：O(1)func getIntersectionNode(headA, headB *ListNode) *ListNode {	i, j := headA, headB  // 两个临时指针，初始分别指向A，B两链表头部
	for {		if i == j {  // 两指针相等时，则为交点，或为nil			return i		}
		if i == nil {  // i指针到末尾后，切换到B链表			i = headB		} else {   // 否则指向A的下一个节点			i = i.Next		}
		if j == nil {  // i指针到末尾后，切换到A链表			j = headA		} else {   // 否则指向B的下一个节点			j = j.Next		}	}}

// helper.go
package intertwolink
import (	"errors"	"strconv")
type ListNode struct {	Val  int	Next *ListNode}
func (l *ListNode) String() string {	s := ""	cur := l	for {		if cur == nil {			s += "nil"			break		}		s += strconv.Itoa(cur.Val) + "->"		cur = cur.Next	}	return s}
// 按数组建立链表func BuildListWithArr(data []int) *ListNode {	if len(data) == 0 {		return nil	}
	root := &ListNode{data[0], nil}	cur := root
	for i := 1; i < len(data); i++ {		node := &ListNode{data[i], nil}		cur.Next = node		cur = node	}
	return root}
// 建立交叉链表// listA，listB 构建链表的数组// intersectVal 为0表示无交点，其他值为交点的值// skipA,skipB 表示链表在交点前的节点数func BuildIntersectList(intersectVal int, ListA, ListB []int, skipA, skipB int) (A, B *ListNode) {	// 构造好链表后再找交点	A = BuildListWithArr(ListA)	B = BuildListWithArr(ListB)	// 无交点	if intersectVal == 0 {		return	}	// 找交点	dummyHeaderA, dummyHeaderB := &ListNode{0, A}, &ListNode{0, B} // 虚拟头节点	curA, curB := dummyHeaderA, dummyHeaderB
	for i := 0; i < skipA; i++ {		if curA.Next == nil {			panic(errors.New("ListA or skipA is incorrect"))		}		curA = curA.Next	}
	for i := 0; i < skipB; i++ {		if curB.Next == nil {			panic(errors.New("ListB or skipB is incorrect"))		}		curB = curB.Next	}
	if curA.Next != nil && curB.Next != nil && curA.Next.Val == intersectVal && curB.Next.Val == intersectVal {		curA.Next = curB.Next	} else {		panic(errors.New("list or skip params incorrect"))	}
	return}

// main_test.go
package intertwolink
import (	"testing")
func TestGetIntersectionNode(t *testing.T) {	arrA := []int{4, 1, 8, 4, 5}	arrB := []int{5, 0, 1, 8, 4, 5}	ListA, ListB := BuildIntersectList(8, arrA, arrB, 2, 3)	interNode := getIntersectionNode(ListA, ListB)	if interNode == nil || interNode.Val != 8 {		t.Error("expect 8,get ", interNode)	}
	arrA = []int{0, 9, 1, 2, 4}	arrB = []int{3, 2, 4}	ListA, ListB = BuildIntersectList(2, arrA, arrB, 3, 1)	interNode = getIntersectionNode(ListA, ListB)	if interNode == nil || interNode.Val != 2 {		t.Error("expect 2,get ", interNode)	}
	arrA = []int{2, 6, 4}	arrB = []int{1, 5}	ListA, ListB = BuildIntersectList(0, arrA, arrB, 3, 1)
	interNode = getIntersectionNode(ListA, ListB)	if interNode != nil {		t.Error("expect nil,get ", interNode)	}}