Leetcode 142. Linked List Cycle II

  1. 云栖社区>
  2. 博客>
  3. 正文

Leetcode 142. Linked List Cycle II

唐非凡 2019-01-06 15:44:25 浏览398
展开阅读全文

地址:Leetcode 142. linked list Cycle II

问题描述:检测链表是否存在环,是的话返回环入口,否则返回None.

这道题有两个思路,一个是经典的快慢指针的思路,另外一个是利用hashMap来记住已经访问过的Node。

思路一:检测到环的时候,令慢指针指向head,然后fast 和 slow指针皆一次移动一个,到他们再次相遇的时候就是环的入口。
简单证明如下,来自Leetcode网友:

代码:

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        slow,fast = head,head
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next.next
            if (slow == fast):
                slow = head
                while(slow!=fast):
                    slow = slow.next
                    fast = fast.next
                return slow  #返回入口节点
        return None

思路二:利用一个hashMap当再次访问节点的时候就是环的入口。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        visited = {}
        p = head
        while(p):
            if visited.get(p) != None:
                return p
            else:
                visited[p] = True
            p = p.next
        return None

最后总结来自:will_duan博客

目前我遇到的主要有以下几点应用:

  • 如上面第一题,判断一个链表是否有环
  • 如上面第二题,求一个链表是否存在环,如果存在,则求出环的入口结点
  • 另一个应用是求链表是否存在环的变式,如给定两个链表A和B,判断两个链表是否相交,解决方法就是将A链表尾节点指向头结点形成一个环,检测B链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
  • 求有序链表中求出其中位数,这种问题也是设置快慢指针,当快指针到底链表尾部的时候,慢指针刚好指向链表中间的结点。

网友评论

登录后评论
0/500
评论
唐非凡
+ 关注