Last Updated: 4 Dec, 2020
Deletion in Circular Linked List
Easy
Asked in company
You are given a Circular Singly Linked List of integers. Given a value ‘VAL’, delete the first occurrence of this value in the linked list. If the given value is not present, return the same linked list.
A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element. This means that the circular linked list is similar to the single linked list except that the last node points to the first node in the list.
Example:
Input Format:
The first line of input contains an integer 'T', the number of test cases. Then each test case follows.
The first line of each test case contains the elements of the circular linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
The second line contains an integer ‘VAL’, the value of the node to be deleted.
Output Format:
For each test case, print the circular linked list after deletion. The elements of the list will be single-space separated, terminated by -1.
The output of each test case is printed in a separate line.
Note :
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints :
1 <= 'T' <= 10
1 <= 'N' <= 5 * 10^4
-10^9 <= 'data' <= 10^9 'and 'data' != -1
-10^9 <= 'VAL' <= 10^9 and 'VAL' != -1
Where 'N' denotes the number of elements in the Circular Singly Linked List and 'data' represents the value of those elements.
Time Limit: 1 sec
Approaches
There will be two cases for deleting a node in a linked list.
Case 1: When the list contains only one node.
- This case exists when, ‘head->next == head’.
- If ‘head->data’ is not equal to ‘VAL’, it means that the given value is not present in the linked list. Hence, we will return the same linked list.
- If ‘head->data’ is equal to ‘VAL’, then we will return NULL because, after deletion, the list becomes empty.
Case 2: The list contains more than one element.
We will traverse the list until we find the node to be deleted. We define a pointer ‘cur' and initialize it with the head node.
- If ‘cur->next->data’ is equal to ‘VAL’, means we found the node which we have to delete. Now we will delete the ‘cur->next’ node and change the ‘next’ value of ‘cur’ such that it points to the node which is next to the deleted node. If the deleted node is head, then the new head will be ‘head->next’.
- If ‘cur->next’ is equal to head, it means that ‘VAL’ is not present in the list. Hence, we will return the same list.