关于golang:Leetcode专题链表面试题-0207链表相交

42次阅读

共计 871 个字符,预计需要花费 3 分钟才能阅读完成。

力扣链接:
https://leetcode-cn.com/probl…
解题思路:

  1. 首先还是之前的论断,在拿到题目的时候,要先找寻法则,从题干中找出有用的信息,这道题题干中 请你找出并返回两个单链表相交的起始节点,这里阐明如果有相交的节点,那么在这个节点之后两个链表是完全相同的,也就是说,从某个节点开始,绝对较短的节点跟绝对较长的节点是末端对齐的
  2. 如果没有相交的节点,那就返回 nil
  3. 所以这道题的解法就是:先将两个链表的末端对齐,对齐的方法就是较长的链表先走两个链表的差值步,而后两个链表同时开始走,查找是否有雷同的节点,晓得找到 / 完结
  4. 双指针:快指针指向较长的链表对齐后的节点,慢指针是较短链表的终点
/**
* 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
}

正文完
 0