Linked List: Convert a single linked list to circular linked list

Problem Statement:

Given a SLL, convert into CLL

Solution 1: Using Iteration

Reach the last node of the LL, by checking the next node is NULL.

Point the next of node back to the head.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Using Recursion

Reach the last node of the LL, by checking the next node is NULL.

Point the next of node back to the head.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream> 
using namespace std; 


class Node 
{

  public:
    int data;

    Node *next;

    Node(int x) 
    {
        data = x;
        next = NULL;
    }
};

Node *solution_1 (Node *head) 
{


    Node *curr = head;


    while (curr->next != nullptr)
        curr = curr->next;

    curr->next = head;

    return head;
}


void solution_2(Node *curr, Node *head) 
{

    if (curr->next == NULL) 
    {
        curr->next = head;
        return;
    }

    solution_2(curr->next, head);
}

void print_list(Node *head) 
{

    Node *curr = head;

    do 
    {
        cout << curr->data << " ";
        curr = curr->next;

    } while (curr != head);
    cout << endl;
}

int main() 
{

    Node *head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);

    head = solution_1(head);
    
    //solution_2(head, head);

    print_list(head);

    return 0;
}

Output

1 2 3 4