golang力扣leetcode 160.相交链表

160.相交链表

160.相交链表

160.相交链表

题解

思路1:

1.用map存A的所有节点,赋值为true
2.遍历B的节点,如果map[cnt]=true说明就是交点

思路2:

1.统计A的长和B的长,谁长谁先走几步,走到长度一致位置
2.A和B一起走,遇到相同的节点返回即可
3.如果不相交,返回nil

思路3:

1.设链表A的不相交长为m,B不相交从部分为n,相交长为c,即len(A)=m+c,len(B)=n+c
2.循环,A和B一起走,如果A走到nil了,则A赋值为B的头,如果B走到nil了,则B赋值为A的nil
3.则A走了m+c+n,B走了n+c+m
4.m+c+n即走完了一遍A,并且走完了B的不相交部分,刚好停在了相交节点
5.而如果不相交,就是nil了

代码

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	mp := make(map[*ListNode]bool)
	cur := headA
	for cur != nil {
		mp[cur] = true
		cur = cur.Next
	}
	for headB != nil {
		if mp[headB] {
			return headB
		}
		headB = headB.Next
	}
	return nil
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenA := getLength(headA)
	lenB := getLength(headB)
	if lenA > lenB {
		cnt := lenA - lenB
		for i := 0; i < cnt; i++ {
			headA = headA.Next
		}
	} else {
		cnt := lenB - lenA
		for i := 0; i < cnt; i++ {
			headB = headB.Next
		}
	}
	for headA != nil && headB != nil {
		if headA == headB {
			return headB
		}
		headA = headA.Next
		headB = headB.Next

	}
	return nil
}
func getLength(root *ListNode) int {
	ans := 0
	for root != nil {
		ans++
		root = root.Next
	}
	return ans
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	curA, curB := headA, headB
	for curA != curB {
		if curA != nil {
			curA = curA.Next
		} else {
			curA = headB
		}
		if curB != nil {
			curB = curB.Next
		} else {
			curB = headA
		}
	}
	return curA
}

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

cheems~

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付:¥1
获取中
扫码支付

您的余额不足,请更换扫码支付或充值

打赏作者

实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值