Deletion in Circular Linked List

Easy
0/40
profile
Contributed by
0 upvote
Asked in company
Expedia Group

Problem statement

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.

Example:

Circular Linked List

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
10 20 30 40 -1
20
8 9 8 -1
8
4 -1
4
Sample Output 1:
10 30 40 -1
9 8 -1
-1
Explanation For Sample Input 1:
For the first test case:
2nd element ( which has a value of 20 ) will be deleted.

Sample Input 1

For the second test case:
8 occur two times, but only the first occurrence will be deleted.

Sample Input 2

For the third test case, the list has only one element with a value of 4. So after deletion, the list will become empty.

Sample Input 3

Sample Input 2:
2
1 5 4 -1
7
1 1 1 -1
1
Sample Output 2:
1 5 4 -1
1 1 -1
Hint

Traverse the list until you find the node to be deleted.

Approaches (1)
Brute Force

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.
Time Complexity

O(N), where N is the number of nodes in the linked list.
 

We traverse every node in the list only once, thus the final time complexity is O(N).

Space Complexity

O(1).
 

We are using constant space.

Code Solution
(100% EXP penalty)
Deletion in Circular Linked List
Full screen
Console