[数据结构][Python][经典题目]链表问题

水深无声 2022-10-02 01:55 224阅读 0赞

# 题目 #

有一个单项链表，链表有可能出环，如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70]

# 方案1 #

首先从头开始，依次遍历链表中的每一个节点。每遍历一个新节点，就从头检查新节点之前的所有节点，用新节点和此节点之前所有节点一次做比较。如果发现新节点和之前的某个节点相同，则说明改节点被遍历过两次，链表有环；如果之前的所有节点中不存在相同节点，就继续遍历下一个节点，继续重复刚才的操作。  
假设该链表节点数为n，则该算法时间复杂度为O(n^2)，空间复杂度O(1)。

# 方案2 #

首先创建一个以节点ID为Key的HashSet集合，用来存储曾经遍历过的节点。然后同样从节点开始依次遍历单链表中的每一个节点。每遍历一个新的节点，都用新节点和HashSet中存储的节点进行比较，如果发信啊HashSet中不存在与新节点相同的节点ID，就把这个新及诶单ID存入HashSet中，之后进入下一节点，继续重复刚才的操作。  
假设该链表节点数为n，则该算法时间复杂度为O(n)，空间复杂度O(n)。

# 方案3（最佳） #

首先创建两个指针P1和P2，让他们同时指向这个链表的头节点。然后开始一个大循环，再循环体内，让指针P1每次向后移动1个节点，让P2每次移动2个节点。然后比较两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。  
第一步：P1和P2都指向节点5  
第二步：P1指向节点3，P2指向节点7  
第三步：P1指向节点7，P2指向节点6  
第四步：P1指向节点2，P2指向节点1  
第五步：P1指向节点6，P2也指向节点6，说明有环

代码实现：

class Node(object):
        def __init__(self, val, p=0):
            self.data = val
            self.next = p
    def is_cycle(head):
        p1=p2 = head
        while p2 and p2.next:  # 当链表为空或者只有一个结点时，就不执行循环体里的程序，返回False
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                return True
        return False
    
    if __name__ == '__main__':
        node1  = Node(5)
        node2  = Node(3)
        node3  = Node(7)
        node4  = Node(2)
        node5  = Node(6)
    
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        node5.next = node4
        print(is_cycle(node1))

# 扩展 #

## 1、如果链表有环，如何求出环的长度？ ##

当两个指针首次相遇，说明有环的时候，让两个指针从相遇点**继续循环前进**，并统计前进的循环次数，知道两个指针第2次相遇。此时，统计出来的前进次数就是环长。  
因为指针P1每次走1步，指针P2每次走2步，两者的速度相差是1步。当两个指针在次相遇时，P2比P1多走了整整1圈。  
**因此，环长=每次一速度差\*前进次数**

## 2、求入环点 ##

从链表头结点到入环点的距离，等于首次相遇点回到入环点的距离。这样一来，只要把其中一个指针放回到头结点位置，另外一个指针保持在首次相遇点，两个指针都是每次向前1步。那么，他们最终相遇的节点，就是入环点。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70]: /images/20220113/83112a84a9f64e02b63282625dfd1a97.png