Problem Statement: Given a Circular Linked List, insert an element at begin of the circular linked list.
Examples:
Example 1: Input: 1 2 3 4 5 6, newNode=0 Output: 0 1 2 3 4 5 6 Example 2: Input: 10, newNode=9 Output: 9 10 Example 3: Input: NULL, newNode=1 Output: 1
Solution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Approach: O(n) approach
To achieve this, we iterate to the end of the CLL and perform the following operations
- Make the next pointer of the last node to point to the newNode.
- Make the next pointer of the newNode to point to the head node
- Return the newNode as the head of our CLL.
The following diagram gives a simple visualization
Code:
C++ Code
#include <iostream>
using namespace std;
struct node {
int data;
node * next;
node(int d) {
data = d;
next = NULL;
}
};
node * insertion_beg(node * head, int x) {
node * newnode = new node(x);
if (head == NULL) { // CLL is empty
newnode -> next = newnode;
return newnode;
} else {
// O(n) approach
node * current = head;
while (current -> next != head) {
current = current -> next;
}
newnode -> next = current -> next;
current -> next = newnode;
return newnode;
}
}
//printing CLL
void printCLL(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 insertion:"<<endl;
printCLL(head);
head = insertion_beg(head, 9);
cout<<"Before insertion:"<<endl;
printCLL(head);
return 0;
}
Output:
Before insertion:
10 20
Before insertion:
9 10 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 insert_begg(node head, int x) {
node newnode = new node(x);
if (head == null) {
newnode.next = newnode;
return newnode;
} else {
node current = head;
while (current.next != head) {
current = current.next;
}
newnode.next = head;
current.next = newnode;
return newnode;
}
}
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 insertion: ");
printlist(head);
head = insert_begg(head, 15);
System.out.println("After insertion: ");
printlist(head);
}
}
Output:
Before insertion:
10 20 30
After insertion:
15 10 20 30
Time complexity: O(n)
Space complexity: O(1)
Solution 2:
Approach: O(1) approach
This approach is very simple. Here we do the following steps:
- Make the newNode as the second node of our CLL.
- Swap the data of our head node and newNode
- Return the head as our head node of our CLL
The following diagram backs 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 * insertionBeg(node * head, int x) {
node * newnode = new node(x);
//step 1
newnode -> next = head -> next;
head -> next = newnode;
//step 2
swap(newnode -> data, head -> data);
//step 3
return head;
}
void printCLL(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 insertion:"<<endl;
printCLL(head);
head = insertionBeg(head, 9);
cout<<"After insertion:"<<endl;
printCLL(head);
return 0;
}
Output:
Before insertion:
10 20
After insertion:
9 10 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 insert_begg(node head, int x) {
node newnode = new node(x);
if (head == null) {
newnode.next = newnode;
return newnode;
} else {
// step 1
newnode.next = head.next;
head.next = newnode;
//step 2
int swapper = head.data;
head.data = newnode.data;
newnode.data = swapper;
//step 3
return head;
}
}
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 insertion:");
printlist(head);
head = insert_begg(head, 15);
System.out.println("After insertion:");
printlist(head);
}
}
Output:
Before insertion:
10 20 30
After insertion:
15 10 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