关于golang:Leetcode专题链表142环形链表-II

43次阅读

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

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

  1. 题干:给定一个链表的头节点 head,返回链表开始入环的第一个节点。如果链表无环,则返回 null。
  2. 这道题其实是个数学证明题,过后记得 18 年找工作面试百度的时候遇到过,这里做一个思路的记录
  3. 要找到环形列表的入口首先通过寻找链表的环,找到快慢指针的相遇点
  4. 而后从相遇点作为一个指针,链表结尾做一个指针,同时开始遍历,当他们两个相遇时,就是环的入口
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 首先判断链表是否有环
// 定义两个指针,快指针每次走两步,慢指针每次走一步,相遇就阐明链表有环
// 记录相遇的地位,从新定义两个指针,一个指向头指针,一个指向之前相遇的地位
// 同时遍历,相遇的地位就是环的入口
func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil { // 以后节点不为空,以后节点的下一节点不为空
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow { // 找到相遇的节点, 阐明有环
            circleStart := fast
            listStart := head
            for (circleStart != listStart) { 
                circleStart = circleStart.Next
                listStart = listStart.Next
            }
            return circleStart  // 相遇时就是入口
        }
    }
    return nil
}

正文完
 0