Python 检查给定的链表是否是循环链表|极客笔记

Python 检查给定的链表是否是循环链表

在本教程中，我们将编写Python程序来检查给定的链表是否是循环链表。我们将了解确定循环链表的各种有效方法。假设您对链表和循环链表的基本概念已经熟悉（可以跳过介绍部分）。如果您不熟悉链表，请让我们简要概述一下链表。

什么是链表

链表是一种线性数据结构，它存储下一个元素的地址。每个元素称为节点，一个节点由数据和下一个元素的内存地址组成。我们可以通过指针访问链表的元素，第一个节点称为头节点。

与数组相比，链表提供了优势，因为它动态地存储元素，而数组具有固定的大小。在链表中，我们可以轻松地插入和删除元素。

循环链表

循环链表是一种特殊类型的链表，它的最后一个后继指针字段引用链表中的某个元素。另一方面，指针元素的下一个指针字段具有 null 值。当我们遍历整个链表时，如果没有遇到NULL，则存在一个循环。

Python 检查给定的链表是否是循环链表

如何检查给定的链表是循环的

根据链表的定义，当我们遍历链表时可以很容易地找出答案。

如果没有节点指向null。
如果链表中的任何节点指向头或起始节点，则链表是循环的。

让我们了解解决方案。

解决方案-1：

按照以下步骤检查给定的列表是否是循环的。

遍历整个链表。
检查节点是否指向头部。
如果返回true，则意味着给定的链表是循环的。

让我们了解下面的代码。

示例

class Node:

    # Function to initialise the current object
    def __init__(self, data):
        self.data = data 
        self.next = None 

# Linked List class contains a current object
class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

def Circular(head):
    if head==None:
        return True

    # Next of head
    current = head.next
    i = 0

    # This loop would stop in both cases (1) If
    # Circular (2) Not circular
    while((current is not None) and (current is not head)):
        i = i + 1
        current = current.next

    return(current==head)


node = LinkedList()
node.head = Node(1)
second =  Node(2)
third =  Node(3)
fourth = Node(4)

node.head.next = second;
second.next = third;
third.next = fourth

if (Circular(node.head)):
    print('The given linked list is a circular list')
else:
    print('The given linked list is not a circular list')

fourth.next = node.head

if (Circular(node.head)):
    print('The given linked list is a circular list')
else:
    print('The given linked list is not a circular list')

输出：

The given linked list is not a circular list
The given linked list is a circular list

说明-

在上面的代码中，我们创建了一个Node类来初始化链表的节点。然后我们创建了一个LinkedList类，它将指向链表的头节点；初始为空。最后，我们定义了CircularList函数，该函数确定给定的链表是否是循环链表。

在这个函数中，我们检查头节点是否为空。如果为真，则返回True。如果头节点不为空，则将头节点的下一个元素赋给当前节点，并将i设置为零。然后，我们定义while循环，该循环将在当前节点不为空且当前节点不等于头节点时运行。如果循环终止条件成立，则返回当前节点等于头节点。

解决方案-2：双指针解决方案

我们可以使用两个速度不同的指针来确定给定的链表是否是循环链表。我们定义一个slow指针和一个fast指针。我们使用这些指针遍历链表。slow指针每次移动一步，fast指针每次移动两步。

如果链表不是循环链表，那么快指针将会到达下一个指针为空的元素的末尾。

让我们理解这个方法。

检查头节点是否为空，返回false。
如果不为空，则创建两个指针slow和fast => slow=head，fast = head.next。
运行一个循环，直到slow等于fast。
循环内部，如果fast为null或者下一个元素为null，则返回false。
如果不是，则赋值 => slow = slow.next，fast = fast.next.next。
返回true。

让我们将上述方法实现为Python代码。

示例

class Node:

    # Function to initialise the current object
    def __init__(self, data):
        self.data = data 
        self.next = None 

# Linked List class contains a current object
class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

def circular_list(head):
    if head is None:
        return "The Given list is a circular list"
    slow = head
    fast = head.next

    while slow != fast:
        if fast is None or fast.next is None:
            return "The Given list is a circular list"

        slow = slow.next
        head = fast.next.next

    return "The Given list is a circular list"


node = LinkedList()
node.head = Node(1)
second =  Node(2)
third =  Node(3)
fourth = Node(4)

node.head.next = second;
second.next = third;
third.next = fourth

print(circular_list(node.head))

输出：

The Given list is a circular list

解释 –

我们创建了Node和LinkedList类来初始化上面代码中的node和head。然后我们创建了circular_list()函数，它以head作为参数。如果head为none，则没有链表；否则，我们将慢指针分配为head，快指针分配为head的下一个元素。然后，如果链表中slow不等于fast，迭代链表。在循环中，我们检查fast指针是否为none或fast的下一个元素是否为none；如果条件为真，则返回链表不是一个循环链表。否则，我们将slow.next元素分配给慢指针，将fast.next.next元素分配给快指针。如果慢指针和快指针相等，则表示给定的链表是一个循环链表。循环结束并返回true以指示循环链表。