Delete head of Circular Linked List

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