Linked List: Perform below operations from a circular linked list

1. Delete at beginning
2. Delete at specific position
3. Delete at end

1. Delete at beginning

To delete the first node, we check if the list is empty, if the list is empty, then return NULL.

If the list contain only one node, then head and last node are same. Then we delete the node and set the last pointer to NULL.

If there are multiple nodes, then we update last->next to head->next, delete the head node. Then return the last node in the list.

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

2. Delete at specific position

Check if the list is empty, if empty, then return NULL.

If the list has only 1 node, and the key matches, then delete the node, set the last node to NULL.

3. Delete at end

Check if the list is empty then return NULL.

If the list has only one node, then delete and return NULL.

else, traverse till the end of the list and delete the last node and set the second last next pointer to NULL.

Code Solution

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct Node
{
	int data;
	Node *next;

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

void print_list(Node *head)
{
	Node *start = head;

	while(start)
	{
		cout<<start->data<<" -> ";
		start = start->next;
	}
	cout<<"\n";
}

Node* deleteHeadNode(Node* head) {
  
    if (head == nullptr)
        return nullptr;

    Node* temp = head;

    head = head->next;

    delete temp;

    return head;
}

Node* deleteNodeAtGivenPosition(Node* head, int position)
{
    Node* prev;
    Node* temp = head;

    if (temp == NULL)
        return head;

    if (position == 1) {
        head = temp->next;
        free(temp);
        return head;
    }

    for (int i = 1; i != position; i++) {
        prev = temp;
        temp = temp->next;
    }

    if (temp != NULL) {
        prev->next = temp->next;
        free(temp);
    }
    else {
        cout << "Node not present\n";
    }

    return head;
}


Node* deleteLastNode(struct Node* head)
{
    
    if (head == NULL) {
        return NULL;
    }

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


    Node* second_last = head;

    while (second_last->next->next != nullptr) {
        second_last = second_last->next;
    }

    delete (second_last->next);

    second_last->next = nullptr;

    return head;
}


int main()
{
	Node *head = new Node(2);
	head -> next = new Node(1);
	head -> next -> next = new Node(4);
	head -> next -> next -> next = new Node(3);
	head -> next -> next -> next  -> next = new Node(6);
	head -> next -> next -> next  -> next -> next = new Node(5);

	cout<<"The original list = "<<endl;
	print_list(head);

	head = deleteHeadNode(head);
	print_list(head);

	int position = 2;
	head = deleteNodeAtGivenPosition(head, position);
	print_list(head);

	head = deleteLastNode(head);
	print_list(head);


	return 0;
}

Output

The original list = 
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 
1 -> 4 -> 3 -> 6 -> 5 -> 
1 -> 3 -> 6 -> 5 -> 
1 -> 3 -> 6 ->