Leetcode 141&142 环形链表

题目 141

思路

方法一：

1. 使用一个stack储存遍历过得节点
2. 一直找到重复节点，那么就是环形链表
3. 时间复杂度O(n), 空间复杂度O(n)

方法二

1. 设置两个指针，一个快指针和一个慢指针
2. 将环形类比成一个跑道，只要两个指针移动的速度不一样，那么他们总可以相遇，如果他们相遇，那么链表有环
3. 要考虑当链表为空的特殊情况
4. 时间复杂度O(n), 空间复杂度O(1)

class Solution(object):
    def hasCycle1(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return False
        stack = set()
        while head:
            if head in stack:
                return True
            stack.add(head)
            head = head.next
        return False


    def hasCycle2(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return False
        
        slow = head
        fast = head
        while fast and fast.next:
            if slow == fast:
                return True
            slow = slow.next
            fast = fast.next.next
        return False

题目 142

思路

这道题与上到题的不同之处是要返回链表入环之后的节点，也是有两种方法

方法一

1. 利用集合遍历储存链表中的节点，一旦发现有重复节点，则返回这个节点

class Solution(object):
    def getIntersect(self, head):
        _set = set()
        cur = head
        while cur:
            if cur not in _set:
                _set.add(cur)
                cur = cur.next
            else:
                return cur.val
        return None

方法二

1.与141方法二类似，但是这里提出一个新的点，就是双指针第一次相遇的到入环节点的距离等于头节点到入环节点的距离

class Solution(object):
    def getIntersect(self, head):
        if head == None:
            return None
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                post = fast
                pre = head
                while post != pre:
                    pre = pre.next
                    post = post.next
                return pre
        return None