Problem Statement: Given a circular linked list, delete the head of the circular linked list.
Examples:
Example 1: Input: 1 2 3 4 5 Output: 2 3 4 5 Example 2: Input: NULL Output: NULL Example 3: Input: 1 Output: NULL
Solution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Approach 1: O(n) approach
In this approach, we iterate to the last node of the circular linked list and perform the following steps:
- Point the next pointer of the last node to point to the second node of the linked list.
- Delete the head of the linked list
- Return the second node as the new head of the linked list.
The following diagram explains the above approach
Code:
C++ Code
#include <iostream>
using namespace std;
struct node {
int data;
node * next;
node(int d) {
data = d;
next = NULL;
}
};
node * deletion_begg(node * head) {
if (head == NULL) return NULL;
if (head -> next == head) {
delete head;
return NULL;
}
node * current = head;
while (current -> next != head) {
current = current -> next;
}
current -> next = head -> next; // step 1
delete head; // step 2
return current -> next; // step 3
}
void printLL(node * head) {
node * current = head;
do {
cout << current -> data << " ";
current = current -> next;
} while (current != head);
cout<<endl;
}
int main() {
node * head = new node(10);
head -> next = new node(20);
head -> next -> next = head;
cout<<"Before deletion:"<<endl;
printLL(head);
head = deletion_begg(head);
cout<<"After deletion:"<<endl;
printLL(head);
return 0;
}
Output:
Before deletion:
10 20
After deletion:
20
Time Complexity: O(n)
Space Complexity: O(1)
Java Code
class node {
int data;
node next;
node(int d) {
data = d;
next = null;
}
}
public class Main {
static node deletion_begg(node head) {
if (head == null) {
return null;
}
if (head.next == head) {
return null;
} else {
node current = head;
while (current.next != head) {
current = current.next;
}
current.next = head.next; // step 1
// step 2 : Thanks to java garbage collection mechanism
return current.next; // step 3
}
}
public static void printlist(node head) {
if (head == null) return;
node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String args[]) {
node head = new node(10);
head.next = new node(20);
head.next.next = new node(30);
head.next.next.next = head;
System.out.println("Before deletion:");
printlist(head);
head = deletion_begg(head);
System.out.println("After deletion");
printlist(head);
}
}
Output:
Before deletion:
10 20 30
After deletion:
20 30
Time Complexity: O(n)
Space Complexity: O(1)
Solution 2:
Approach 2: O(1) Approach
In this approach, we perform the following steps:
- Copy the data of the second node into the head node.
- Store the second node in a temp node.
- Change the next pointer of the head node to point to the third node.
- Delete the temp node.
- Return the head.
The following diagram explains the above approach
Code:
C++ Code
#include <iostream>
using namespace std;
struct node {
int data;
node * next;
node(int d) {
data = d;
next = NULL;
}
};
node * deletionBegg(node * head) {
head -> data = head -> next -> data; // step 1
node * temp = head -> next; // step 2
head -> next = head -> next -> next; // step 3
delete temp; // step 4
return head; // step 5
}
void printLL(node * head) {
node * current = head;
do {
cout << current -> data << " ";
current = current -> next;
} while (current!= head);
cout<<endl;
}
int main() {
node * head = new node(10);
head -> next = new node(20);
head -> next -> next = head;
cout<<"Before deletion:"<<endl;
printLL(head);
head = deletionBegg(head);
cout<<"After deletion:"<<endl;
printLL(head);
return 0;
}
Output:
Before deletion:
10 20
After deletion:
20
Time Complexity: O(1)
Space Complexity: O(1)
Java Code
class node {
int data;
node next;
node(int d) {
data = d;
next = null;
}
}
public class Main {
static node deletion_begg(node head) {
// node newnode = new node(x);
if (head == null) {
return null;
}
if (head.next == head) {
return null;
} else {
head.data = head.next.data; // step 1
head.next = head.next.next; //step 3
return head; // step 5
// step 2 & step 4: thanks to JAVA garbage collection mechanism
}
}
public static void printlist(node head) {
if (head == null) return;
node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String args[]) {
node head = new node(10);
head.next = new node(20);
head.next.next = new node(30);
head.next.next.next = head;
System.out.println("Before deletion:");
printlist(head);
head = deletion_begg(head);
System.out.println("After deletion");
printlist(head);
}
}
Output:
Before deletion:
10 20 30
After deletion
20 30
Time Complexity: O(1)
Space Complexity: O(1)
Special thanks to Yash Mishra for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article