环形链表（python实现）

2022年 11月 16日

环形链表（python实现）

题目描述:
给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

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

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

示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle

思路：
首节点附上两个指针，第一个指针每次只遍历一个节点，第二个指针每次遍历两个节点，直到这两个指针所指的节点相同时，则说明有环。

代码：

import chaintable as c

class Solution(c.chainTable):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        node1=head  #走一步
        node2=head  #走两步
        
        while node1.next_node and node2.next_node.next_node:
            node1=node1.next_node
            node2=node2.next_node.next_node
            if node1==node2:
                return True
        return False
    
    
if __name__=='__main__':
    chain=c.chainTable()
    head = [3,2,0,-4]
    pos=1
    for i in head:
        chain.append(i)
    if not pos==-1:
        n1=chain.head
        n2=chain.head
        index=0
        while n1.next_node and index<pos:
            n1=n1.next_node
            index+=1
            
        index=0
        while n2.next_node and index<len(head)-1:
            n2=n2.next_node
            index+=1
            
        n2.next_node=n1
    
    result=Solution().hasCycle(chain.head)
    print(result)

链表的实现：

class Node:
    '''
    定义节点类
    data:节点保存的数据
    next_node:下一个节点对象
    '''
    def __init__(self,data,pnext=None):
        self.data=data
        self.next_node=pnext
    def __repr__(self):
        '''
        定义Node的字符输出
        print为输出data
        '''
        return str(self.data)
'''
链表类：
属性：
链表头：head
链表长度：length
方法：以下
'''
class chainTable:
    def __init__(self):
        self.head=None
        self.length=0
    '判断是否为空列表'
    def isEmpty(self):
        return self.length==0
    
    '在链表尾增加一个节点'
    def append(self,dataorNode):
        item = None
        if isinstance(dataorNode, Node):
            item = dataorNode
        else:
            item = Node(dataorNode)
        if not self.head:
            self.head=item
            self.length+=1
        else:
            node=self.head
            '循环至最后一个节点'
            while node.next_node:
                node=node.next_node
                
            node.next_node=item
            self.length+=1
        
    '删除一个节点'
    def delete(self,index):
        if self.isEmpty():
            print("Sorry,the chain table is empty")
            return
        if index<0 or index>=self.length:
            print("Error:out of index")
            return
        if index==0:
            self.head=self.head.next_node
            self.length-=1
            return
        
        Index=0
        node=self.head
        pre_node=self.head
        while node.next_node and Index<index:
            pre_node=node
            node=node.next_node
            Index+=1
        
        if Index==index:
            pre_node=node.next_node
            self.length-=1
    
    '修改一个节点'
    def update(self,index,data):
        if self.isEmpty()or index<0 or index>=self.length:
            print("Error:out of index")
            return
        
        Index=0
        node=self.head
        while node.next_node and Index<index:
            node=node.next_node
            Index+=1
        if Index==index:
            node.data=data
    
    '查找并得到一个节点'
    def getItem(self,index):
        if self.isEmpty()or index<0 or index>=self.length:
            print("Error:out of index")
            return
        
        Index=0
        node=self.head
        while node.next_node and Index<index:
            node=node.next_node
            Index+=1
        return node.data
    
    '查找一个节点的索引'
    def getIndex(self,data):
        if self.isEmpty():
            print("Sorry,the chain table is empty")
            return
        Index=0
        node=self.head
        while node:
            if node.data==data:
                return Index
            node=node.next_node
            Index+=1
        if Index==self.length:
            print("\"%s is not found\",%str(data)")
            return
        
    '插入一个节点'
    def Insert(self,index,dataorNode):
        if self.isEmpty():
            print("Sorry,the chain table is empty")
            return
        if index<0 or index>=self.length:
            print("Error:out of index")
            return
        item=None
        if isinstance(dataorNode,Node):
            item=dataorNode
        else:
            item=Node(dataorNode)
        
        if index==0:
            item.next_node=self.head
            self.head=item
            self.length+=1
            return
        
        Index=0
        node=self.head
        prev=self.head
        while node.next_node and Index<index:
            prev=node
            node=node.next_node
            Index+=1
        if Index==index:
            item.next_node=node
            prev.next_node=item
            self.length+=1
            
    '清空链表'
    def clear(self):
        self.head=None
        self.length=0
    
    def __repr__(self):
        if self.isEmpty():
            return "The chain table is empty"
        node=self.head
        nlist=''
        i=0
        while Node:
            
            if node.next_node:
                nlist+=str(node.data)+'->'
                node=node.next_node
            else:
                nlist+=str(node.data)+'->None'
                node=node.next_node
                
        return nlist
    
    def __getitem__(self, ind):
        if self.isEmpty() or ind < 0 or ind >= self.length:
            print("error: out of index")
            return
        return self.getItem(ind)
    def __setitem__(self, ind, val):
        if self.isEmpty() or ind < 0 or ind >= self.length:
            print("error: out of index")
            return
        self.update(ind, val)
    def __len__(self):
        return self.length