5 Best Ways to Convert a Singly Linked List to a Circular List in Python

Rate this post

πŸ’‘ Problem Formulation: You have a singly linked list where each node points to the next node and the last node points to None. The task is to convert this list into a circular linked list, where the last node will point back to the first node, creating a loop. If our singly linked list is A -> B -> C -> None, we want to transform it into A -> B -> C -> A (circular).

Method 1: Iterative Approach

This method involves iterating through the list until we find the last node, then we set the next pointer of this node to the head, making it circular. It does not require extra space and maintains the original structure of the list.

Here’s an example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def convert_to_circular(head):
    if head is None:
        return None
    current = head
    while current.next:
        current = current.next
    current.next = head
    return head

# Example Usage:
head = Node('A')
head.next = Node('B')
head.next.next = Node('C')
convert_to_circular(head)

Output: The last node ‘C’ now points to the head node ‘A’, creating a circular linked list.

This code snippet defines a Node class to represent each element in the list. The convert_to_circular function iterates through the list until it finds the last node, then points its next reference back to the head, effectively converting the list into a circular one.

Method 2: Recursive Approach

A recursive approach to converting a singly linked list to a circular list involves defining a base case for the function to return once the end of the list is reached and recursively calling the function to link the last node to the head.

Here’s an example:

def convert_to_circular_recursive(node, head):
    if node.next is None:
        node.next = head
        return head
    return convert_to_circular_recursive(node.next, head)

# Example Usage:
convert_to_circular_recursive(head, head)

Output: Similar to the iterative approach, the last node will reference the head node, forming a circular linked list.

The code uses a recursive function convert_to_circular_recursive that keeps calling itself with the next node, until it reaches the end of the list, at which point it connects the last node to the head of the list.

Method 3: Two-Pointer Technique

The two-pointer technique involves using two pointers to traverse the list. The fast pointer moves two steps at a time, and the slow pointer moves one step. When the fast pointer reaches the end, the slow pointer will be at the preceding node to the last node, and we can then link the last node to the head.

Here’s an example:

def convert_to_circular_two_pointer(head):
    if head is None:
        return None
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    slow.next.next = head
    return head

# Example Usage:
convert_to_circular_two_pointer(head)

Output: The list will be converted into a circular linked list by making the last node point to the head node.

This example uses two pointers to traverse the list. When the faster pointer (moving two steps at a time) reaches the end, we use the slow pointer to set the next node’s next reference to the head, turning it into a circular linked list.

Method 4: Using a List to Store Nodes

Using a list to store nodes involves iterating through the list and pushing each node to a Python list. The last element of this list is the tail, and we can directly access the head using the zeroth index of the list. We then link tail to head.

Here’s an example:

def convert_to_circular_list(head):
    nodes = []
    current = head
    while current:
        nodes.append(current)
        current = current.next
    nodes[-1].next = nodes[0]
    return head

# Example Usage:
convert_to_circular_list(head)

Output: All nodes are added to a list, and the last node in this list is linked to the first node, converting it into a circular list.

This method collects all nodes into a list as it iterates through the linked list. After collecting all nodes, it links the last node’s next reference to the head node, found at index zero of the list, forming a circular list.

Bonus One-Liner Method 5: Using a Tail Reference

If a tail reference is maintained alongside the head of the list, converting the linked list to a circular list can be done in one line by setting the tail’s next pointer to the head.

Here’s an example:

tail.next = head  # Assuming 'tail' is the last node and 'head' is the first node

Output: The list is instantly converted into a circular linked list as the tail now points to the head.

By maintaining a reference to the tail of the list, you can instantly convert the list into a circular one by setting the tail’s next reference to the head of the list. This method is contingent on keeping the tail updated when the list changes.

Summary/Discussion

  • Method 1: Iterative Approach. This method is straightforward and has no additional space complexity. However, it requires traversing the entire list to find the last node.
  • Method 2: Recursive Approach. It is a simpler and more elegant solution but may not be as intuitive to understand at first. The recursion can lead to a stack overflow for very large lists.
  • Method 3: Two-Pointer Technique. It can be more efficient in some cases, but its utility is limited in this context because it doesn’t reduce the number of nodes visited compared to the iterative method.
  • Method 4: Using a List to Store Nodes. This method provides direct access to any nodes but involves additional space complexity proportional to the size of the list.
  • Method 5: Using a Tail Reference. This is the fastest and most efficient method but requires constant maintenance of the tail reference which can be cumbersome for some implementations.