共计 871 个字符,预计需要花费 3 分钟才能阅读完成。
力扣链接:
https://leetcode-cn.com/probl…
解题思路:
- 首先还是之前的论断,在拿到题目的时候,要先找寻法则,从题干中找出有用的信息,这道题题干中 请你找出并返回两个单链表相交的起始节点,这里阐明如果有相交的节点,那么在这个节点之后两个链表是完全相同的,也就是说,从某个节点开始,绝对较短的节点跟绝对较长的节点是末端对齐的
- 如果没有相交的节点,那就返回 nil
- 所以这道题的解法就是:先将两个链表的末端对齐,对齐的方法就是较长的链表先走两个链表的差值步,而后两个链表同时开始走,查找是否有雷同的节点,晓得找到 / 完结
- 双指针:快指针指向较长的链表对齐后的节点,慢指针是较短链表的终点
/** | |
* Definition for singly-linked list. | |
* type ListNode struct { | |
* Val int | |
* Next *ListNode | |
* } | |
*/ | |
// 实质上还是快慢指针的思维 | |
// 先把两个链表尾部对齐 | |
// 而后同时开始遍历 | |
func getIntersectionNode(headA, headB *ListNode) *ListNode { | |
curA, curB := headA, headB | |
lenA, lenB := 0, 0 | |
// 求链表 A 的长度 | |
for curA != nil { | |
curA = curA.Next | |
lenA++ | |
} | |
// 求链表 B 的长度 | |
for curB != nil { | |
curB = curB.Next | |
lenB++ | |
} | |
// 求 A 和 B 的差值 | |
diffLen := diffLen(lenA, lenB) | |
var fast, slow *ListNode | |
// 长度更长的先走 difflen 步 | |
if lenA > lenB { | |
fast = headA | |
slow = headB | |
} else { | |
fast = headB | |
slow = headA | |
} | |
for i := 0; i < diffLen; i++ {fast = fast.Next} | |
// 同时开始走 | |
for fast != slow { | |
fast = fast.Next | |
slow = slow.Next | |
} | |
return fast | |
} | |
func diffLen(a, b int) int { | |
if a > b {return a - b} | |
return b - a | |
} |
正文完