前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >链表-如何快速找出一个环形链表入环处,O(1)空间复杂度能否?

链表-如何快速找出一个环形链表入环处,O(1)空间复杂度能否?

作者头像
阿伟
发布2019-08-08 17:25:56
1.1K0
发布2019-08-08 17:25:56
举报
文章被收录于专栏:GoLang那点事
问题

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。说明:不允许修改给定的链表。

示例1

输入:head = [3,2,0,-4], pos = 1 输出:tail connects to node index 1 解释:链表中有一个环,其尾部连接到第二个节点。

示例二

输入:head = [1,2], pos = 0 输出:tail connects to node index 0 解释:链表中有一个环,其尾部连接到第一个节点。

解法一

我们看到在这个链表的末尾连接的下一个节点是链表上的随机一个点,形成一个环形链表,创建一个map,遍历这个链表,key是这个链表的节点,每次map进行put时,判断是否存在,如果存在,说明遇到重复的了,则此时这个节点就是入环处

代码语言:javascript
复制
type ListNode struct {
     Val int
     Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
   if head == nil{
        return nil
    }
    temp1 := head
    result := head
    //注意map的key不再是指针类型,而是结构体类型
    m := make(map[ListNode]int)
    for temp1 != nil{
        // 通过*取指针变量存储的地址值
        current := *temp1
        if _,ok := m[current];ok{
            result = temp1
            break
        }else{
            m[current] = 1
        }
        temp1 = temp1.Next
        fmt.Println(temp1)
        if temp1 == nil{
            return nil
        }  
    }
    return result
}
解法二

上面的方法是利用一个map,在遍历链表的时候,不断往里面放入当前节点,直到发现有key冲突,则终止,返回当前节点就是入环处,空间复杂度为O(n),那有更好的方法吗?O(1)的空间复杂度呢?说一个新的方法,我们声明两个临时指针变量,one,two,one变量在遍历链表时每次都指向下一个节点,two则指向下一个节点的下一个节点,当one和two相遇时,two就已经走了one的两倍的长度了,此时我们声明一个临时指针变量temp,从头部开始遍历,每此遍历都指向下一个节点,one同样,当temp和one相遇时,则这个节点就是入环处,这是什么原理呢?看下图

这个时候我们temp距离1节点处走两步,one节点距离1节点处也是走两步,为什么这么巧呢?我们知道two走的路是one走的路的两倍,也就是现在说two不动,one还需要走同样的路才能再次和two相遇,这个同样的路也就是temp到one当前节点需要走的路,因为这也是one之前走过的路,他们有一个共同的交点就是入环处,代码如下:

代码语言:javascript
复制
type ListNode struct {
     Val int
     Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
   if head == nil{
        return nil
    }
    //两个快慢指针变量
    one,two := head,head
    for two != nil{
        next := two.Next
        //说明不存在环形链表
        if next == nil || next.Netx{
            return nil
        }
        one = one .Next
        two = next.Next
        //相遇时终止
        if one == two {
            break;
        }
    }
    temp := head
    //相遇时终止
    for temp != one{
        temp = temp.Next
        one = one.Next
    }
    return temp
}

欢迎大家关注微信公众号:“golang那点事”,更多精彩期待你的到来

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 GoLang那点事 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题
  • 示例1
  • 示例二
  • 解法一
  • 解法二
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档