检查链表是否为循环链表的算法

1. Introduction

In Computer Science, a linked list is a linear data structure in which a pointer in each element determines the order.

In this tutorial, we’ll show how to check if a linked list is a circular linked list.

2. Circular Linked List

Each element of a linked list contains a data field to store the list data and a pointer field to point to the next element in the sequence. We can use a head pointer to point to the start element of a linked list:

linkedlist regular

In a regular linked list, the last element has no next element. Therefore, its next pointer field is null . However, in a circular linked list, the last element has a reference to one of the elements in the list:

3. Hash Table Solution

It is easy to see that if a linked list contains a cycle, we’ll eventually visit the same node twice when we traverse the linked list. Therefore, we can use a hash table to solve this problem:

algorithm isCircularList(head):
    // INPUT
    //     head = first element of a linked list
    // OUTPUT
    //     true if the linked list is circular, otherwise false

    hashTable <- construct empty hash table
    currentNode <- head

    while currentNode != null:
        if hashTable contains currentNode:
            return true
        else:
            add currentNode into hashTable

        currentNode <- currentNode.next

    return false

This algorithm traverses the linked list and records each node’s reference in a hash table. We use a linked list node’s reference as its unique identifier. If we see the same reference again in the hash table, we can return true to indicate a circular linked list. Otherwise, we’ll finally reach the null node and return false .

Let’s assume each hash table operation, such as insertion and searching, takes O(1) time. Then, this algorithm’s overall time complexity is O(n) as we traverse the whole linked list only once. The space complexity is also O(n) , as we need to store all the nodes into the hash table.

4. Solution With Two Pointers

To detect whether a linked list is a circular linked list, we can use two pointers with different speeds: a pointer and a pointer. We use these two pointers to traverse the linked list. The slow pointer moves one step at a time, and the fast pointer moves two steps.

If there is no cycle in the list, the fast pointer will eventually reach the last element whose next pointer is null and stop there.

For a circular linked list, let’s imagine the slow and fast pointers are two runners racing around a circular track. At the beginning, the fast runner passes the slow runner. However, it’ll eventually meet the slow runner again from behind. We can use the same idea to detect if there is a cycle in the linked list:

algorithm isCircularList(head):
    // INPUT
    //     head = first element of a linked list
    // OUTPUT
    //     true if the linked list is circular, otherwise false

    if head is null:
        return false

    slow <- head
    fast <- head.next

    while slow != fast:
        if fast is null or fast.next is null:
            return false

        slow <- slow.next
        fast <- fast.next.next

    return true

In this algorithm, we first have a sanity check on the input head pointer. Then, we start two pointers, slow and fast , at different locations. In the loop, we advance the two pointers at different speeds. If the fast pointer reaches the terminated null pointer, we can conclude that the linked list does not have a cycle. Otherwise, the two pointers will eventually meet. Then, we finish the loop and return true to indicate a circular linked list.

5. Complexity Analysis of the Two-pointer Solution

If the linked list doesn’t have a cycle, the loop will finish when the fast pointer reaches the end. Therefore, the time complexity is O(n) in this case.

For a circular linked list, we need to calculate the number of steps to make the fast pointer catch the slow pointer. Let’s first break down the movement of the slow pointer into two stages.

In the first stage, the slow pointer takes steps to enter the cycle. At this point, the fast pointer has already in the cycle and is elements apart from the slow pointer in the linked list direction. In the following example, the distance between the two pointers is 3 elements since we need to advance the fast pointer 3 elements to catch the slow pointer in the cycle:

linkedlist slow fast

In the second stage, both pointers are in the cycle. The fast pointer moves 2 steps in each iteration, and the slow pointer moves 1 step. Therefore, the fast pointer can catch up 1 element in each iteration. Since the distance between these two pointers at the beginning is , we need iterations to make these two pointers meet.

Therefore, the total running time is O(K+D) , where is the number of elements between the head and the start element of the cycle, and is the distance between the two pointers when the slow pointer reaches the cycle. Since is at most the cycle length, the overall time complexity is also O(n) .

The space complexity is O(1) as we only use two pointers ( slow and fast ) in the algorithm.

6. Conclusion

In this tutorial, we showed a sample circular linked list. Also, we discussed two linear-time algorithms that can check if a linked list is a circular linked list.

Persistence

REST

Security