吃透链表 - 计算机科学 | ColaHub = A Simple Blog

# 环形链表

【题目链接】：环形链表
【题目描述】
给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意： pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。
【示例】

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

# 哈希表

判定是否是个环的条件为某个结点的 next 指针是否指向已经遍历过的结点。因此可以使用哈希表存储已经访问过的节点，每当到达一个节点时，判断其是否在哈希表里面，如果在则证明存在环，如果不在就说明不存在。

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

【复杂度分析】

时间复杂度： $O(N)$ ，其中 $N$ 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
空间复杂度： $O(N)$ ，其中 $N$ 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

# 双指针 (快慢指针)

每当慢指针 slow 前进一步，快指针 fast 就前进两步.

如果最终快慢指针相遇，则证明存在环。如果快指针遇到空指针，则不存在环。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        ##快慢指针
        slow,fast=head,head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if fast==slow:
                return True
        return False

【时间复杂度】
$O(N)$ 其中 $N$ 是链表中的节点数。

当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 $N$ 轮。
【空间复杂度】
$O(1)$ 只使用了两个指针的额外空间。

# 环形链表 II

【题目链接】
环形链表

【题目描述】
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null 。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1 ，则在该链表中没有环。注意： pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

【示例】

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

# 哈希表

哈希表依旧是比较简单理解的方法，将访问过的节点存储到哈希表中，每当遍历的节点存在于哈希表中，则返回当前节点。如果访问到最后都不能在哈希表中找到节点，则证明无环，返回 None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        node_dic=dict()
        while head:
            if head in node_dic:
                return head
            node_dic[head]=index
            head=head.next
        return None

# 双指针 (快慢指针)

# 随机链表的复制

随机链表的复制

【示例】

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出： [[7,null],[13,0],[11,4],[10,2],[1,0]]

# 哈希表

用哈希表存储新创建的节点，算法一共包括两个遍历，第一个遍历创建全新的节点，存储格式为 key=old_node,value=new_node 。第二个遍历为新节点建立关系信息，主要为 next 和 random 信息。

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head: return
        cur=head
        new_node=dict()
        while cur:
            new_node[cur]=Node(cur.val)
            cur=cur.next
        cur=head
        while cur:
            #构建next
            new_node[cur].next=new_node.get(cur.next)
            #构建random
            new_node[cur].random=new_node.get(cur.random)
            cur=cur.next
        return new_node[head]

# 环形链表

# 哈希表

# 双指针 (快慢指针)

# 环形链表 II

# 哈希表

# 双指针 (快慢指针)

# 随机链表的复制

# 哈希表

hexo博客使用

二分查找