-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day_70.cpp
64 lines (52 loc) · 1.33 KB
/
Day_70.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
DAY 70 : Circular Linked List Delete at Position.
https://www.geeksforgeeks.org/delete-middle-of-linked-list/
QUESTION : Given a linked list of size n, you have to delete the node at position pos
of the linked list and return the new head. The position of initial node is 1.
The tail of the circular linked list is connected to the head using next pointer.
Example 1:
Input:
LinkedList: 1->2->3->4->5
(the first and last node are connected,
i.e. 5 --> 1)
position: 4
Output: 1 2 3 5
Example 2:
Input:
LinkedList: 2->5->7->8->99->100
(the first and last node are connected,
i.e. 5 --> 1)
position: 6
Output: 2 5 7 8 99
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(1)
Constraints:
2 <= number of nodes <= 10^3
1 <= pos <= n
*/
Node * deleteAtPosition(Node *head,int pos)
{
if (head == NULL) {
return NULL;
}
Node *curr = head;
Node* prev = NULL;
while(curr->next != head){
curr=curr->next;
}
prev = curr;
curr = head;
pos = pos-1;
if (pos==0){
prev->next = curr->next;
head = curr->next;
}
else{
while(pos--) {
prev=curr;
curr=curr->next;
}
prev->next=curr->next;
}
return head;
}