Best Explanation on TH-cam for this question. I have gone through at least 15+ Videos of this question. But this stands at TOP. Thank you very Much for this amazing series
Completed this series,Very well explained. Anybody who is starting with LinkedList can follow this series without thinking much. Thank you for this series.
Instead of using n separately in copyList, we can just change the pointers as follows... makes the code a lot cleaner and understandable. Node *temp = head; while(temp){ Node *copy = new Node(temp->val); copy->next = temp->next; temp->next = copy; temp = copy->next; }
sir, please make a video on (computer network) preparation in 3 days for placement sir , "you forgot it this subject to make a video " its humble request sir please make a video as soon as possible
On Nishant chahar TH-cam channel,u can find list of important CN topics for Tech interviews,for prep,u can see CN playlist of Gate Smashers TH-cam channel Hope this helps! All the best! 🤗❤️
Algorithm :- 1. Add Duplicate Clone node ahead of original Node in Linked List 2. Handle Random Pointers But Be careful If any Node->Random == NULL 3. Separate Both the linked List and Fix the next Pointer of Original and Cloned List -----------------------------------------------------*------------------*---------------------------------------------------------------- Make a clone of Each Node which is pointed by actual node->next Original : 1-2-3-4-X Clone : 1'-2'-3'-4'-X Step 1 : Merge Actual Node with Clone Node so That Actual->next = clone && clone->next = Actual->next 1--1'--2--2'--3--3'--4--4'--X Step 2 : Now Make Random of Clone = Random of Actual->Next Ex- Random(1) = 3 , So Random(1') = 3' 1->random = 3 , 1->next->random = 1->random(3)->next Step 3 : Take a Dummy Node and Add all Clone nodes to dummy also Fix Next of original List. Head -> 1->2->3->4->X Dummy ->1'->2'->3'->4'->X Step 4 : Return Dummy->Next -----------------------------------------------------*------------------*---------------------------------------------------------------- Node* copyRandomList (Node* head) { if ( head == NULL ) return NULL; Node *curr = head; while(curr){ // Create a new Node That will point to Curr->Next Node *newNode = new Node(curr->val); newNode->next = curr->next;
// Now Curr Will point to newNode curr->next = newNode;
// Now Curr will move to Node 2 or newNode->next curr = newNode->next; }
// Now Fixing The Random Pointer curr = head; while(curr){ if(curr->random==NULL) curr->next->random = NULL; else curr->next->random = curr->random->next; curr = curr->next->next; }
// Now Adjusting The Next Pointers curr = head; Node* curr2 = new Node(-1), *newHead=curr2; while(curr){ // New_Head-->1' curr2->next = curr->next; // Fixing Original Next curr->next = curr->next->next; // Now, Curr will move to next Curr & same with Curr2 curr = curr->next; curr2 = curr2->next; }
Best Explanation on TH-cam for this question. I have gone through at least 15+ Videos of this question. But this stands at TOP. Thank you very Much for this amazing series
Completed this series,Very well explained. Anybody who is starting with LinkedList can follow this series without thinking much. Thank you for this series.
finally finished with this series, thank you for making linked lists easy.
Completed this series in one single day, this feeling can't be gain by watching Netflix series 😌.
Credit goes to bhaiya 🔥
Amazing job bro. Did you also code ?
@@mohammadfraz but i did
@@mohammadfraz bhai aapne toh 30 videos bola tha
God Level Explanation .
Thanks, @FRAZ for this wonderful explanation.
Completed this series in 5 days.. Thanks to Fraz bhai for this amazing series 🔥🔥
Is it the complete series of linked list??
@@vishalsinghshekhawat6921 yes bro
@@saifkhansaleemkhan8965 bhai perquisites kya h iske??
@@vishalsinghshekhawat6921 Linked List Basics and c++ basics
Thanks bhaiya for this amazing series
Waiting for more episodes!
Instead of using n separately in copyList, we can just change the pointers as follows... makes the code a lot cleaner and understandable.
Node *temp = head;
while(temp){
Node *copy = new Node(temp->val);
copy->next = temp->next;
temp->next = copy;
temp = copy->next;
}
Sir please make videos on all topics of DSA
Your way of teaching is amazingly easy and awesome
Love from Pakistan
A very good thing is instead of editing out the ERRORS, u really showed us to debug. that's really great FRAZ. BCoz that is really needed for newbies.
bhaiya is this the last video of the series or you are planning to bring more videos??
Literally worth watching it :)
Is this linked list playlist complete...?
Bhaiya khtm krdi ye ek ek comment krra video pe bhut accha laga bhaiya dono approaches bata diye aap !!!!! Shaandaar video !!!! 🔥🔥
Is this the last video of this playlist...?
Can someone suggest me , I should go with this or not....?
Go with it just finished it today its really nice
edge case of randompointer
void handleRandom(LinkedListNode *
head){
LinkedListNode *temp = head;
while(temp){
if(temp->next){
temp->next->random = temp->random!=NULL ? temp->random->next : NULL;
}
temp = temp->next->next;
}
}
Best series Finished!
Next Episode......eagerly waiting
Thank you ❤️
Today I solved medium level problem based on linked list 🤩
Completed......brooo🥳 Op🔥🔥
1. NAIVE(No Extra Space) APPROACH:-
--------------------------------------------------------------
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return NULL;
// MERGING LISTS
for(Node *l1 = head; l1 != NULL; l1 = l1->next->next){
Node *l2 = new Node(l1->val);
l2->next = l1->next;
l1->next = l2;
}
Node *newHead = head->next;
// ALLOCATING RANDOMS
for(Node *l1 = head; l1 != NULL; l1 = l1->next->next){
if(l1->random != NULL)
l1->next->random = l1->random->next;
}
// SEPERATING LISTS
for(Node *l1 = head; l1 != NULL; l1 = l1->next){
Node *l2 = l1->next;
l1->next = l2->next;
if(l2->next) l2->next = l2->next->next;
}
return newHead;
}
};
// Time Complexity = O(n)
// Space Complexity = O(1)
2. OPTIMIZED/STRUCTURED(No Extra Space) APPROACH - By Fraz Bhaiya (from this lecture):-
----------------------------------------------------------------------------------------------------
class Solution {
private:
void copyList(Node *head){
Node *temp = head, *n = head->next;
while(temp){
Node *copy = new Node(temp->val);
temp->next = copy;
copy->next=n;
temp = n;
if(n) n = n->next;
}
}
void handleRandom(Node *head){
Node *temp = head;
while(temp){
if(temp->random)
temp->next->random = temp->random->next;
temp = temp->next->next;
}
}
Node *detach(Node *head){
Node *dummy = new Node(-1);
Node *temp = head, *tail = dummy;
while(temp){
tail->next = temp->next;
tail = tail->next;
temp->next = tail->next;
temp = temp->next;
}
return dummy->next;
}
public:
Node* copyRandomList(Node* head) {
if(head == NULL) return NULL;
copyList(head);
handleRandom(head);
return detach(head);
}
};
// Time Complexity = O(n)
// Space Complexity = O(1)
-----------------------------------------------------------------------------------------------------------------
Enjoy Guys !!! ❤😉
I wrote here for revision purpose in future but you can use too for revision :)
And Thank to Fraz Bhaiya 🙏🥰❣🔥for whole content :)
Please share link of ur Microsoft interview preparation playlist. Is ur Microsoft prep playlist enough to crack Microsoft interviews?
Bro you can do my DSA sheet for Microsoft preparation
void copyList(LinkedListNode *head){
LinkedListNode * temp = head;
while (temp != nullptr) {
LinkedListNode* newNode = new LinkedListNode(temp->data);
newNode->next = temp->next;
temp->next = newNode;
temp = newNode->next;
}
}
void handleRandom(LinkedListNode *head){
LinkedListNode *temp = head;
while(temp){
// very imp edge case
if(temp->next)
temp->next->random = temp->random!=NULL ? temp->random->next : NULL;
temp = temp->next->next;
}
}
LinkedListNode *detach(LinkedListNode *head){
LinkedListNode *dummy = new LinkedListNode(-1);
LinkedListNode *temp = head;
LinkedListNode *tail = dummy;
while(temp){
tail->next = temp->next;
tail = tail->next;
temp->next = tail->next;
temp = temp->next;
}
return dummy->next;
}
LinkedListNode* extraSpace(LinkedListNode *head){
// space N
map mp;
LinkedListNode * temp = head;
//maping original->new
while (temp) {
LinkedListNode* newNode = new LinkedListNode(temp->data);
mp[temp] = newNode;
temp = temp->next;
}
temp = head;
while (temp) {
mp[temp]->next = mp[temp->next];
mp[temp]->random = mp[temp->random];
temp = temp->next;
}
return mp[head];
}
//driver fun
LinkedListNode *cloneRandomList(LinkedListNode *head)
{
if (!head) return nullptr;
copyList(head);
handleRandom(head);
//remove old
return detach(head);
return extraSpace(head);
}
Is this episode final one, is there no more episodes in Linked List season 3?
Sir plaz graph pe banayiye
sir, please make a video on (computer network) preparation in 3 days for placement
sir , "you forgot it this subject to make a video "
its humble request sir please make a video as soon as possible
On Nishant chahar TH-cam channel,u can find list of important CN topics for Tech interviews,for prep,u can see CN playlist of Gate Smashers TH-cam channel
Hope this helps! All the best! 🤗❤️
Bro ye sab banaya hua hai , sare questions bhi dale hue hain.
Check in interview preparation playlist
thanks bro for this videos 😇
You're welcome ❤️
Bhaiya next episode kb aega ?Btw quality bhot zaada hi high level pe improve krdi h apne
Is this Is the last video of series ???
Is this the last episode?
Bhai recursion par bnado
//Best series for linked list
while(true)
{
Best = Best * infinity;
}
I am a DSA beginner, agr apka free interview series+ 250qtns ki sheet krlu, tech interviews k liye enough hoga?
Haan for DSA it would be enough
waiting
Please help BHAIYA DTU COE vs NSUT CSE
my home is 3km away from DTU
DTU COE lele bhai,advice from 3rd year DTU Student
bhaiya aage ke videos daaldo na, dekhliye saare kabke.
next episode maangta hy mereko bhai
This is the last video of Linked list series or you will upload some more videos in future.
Reach++
hi
Hi
Why you are not using english nowadays sir?
Please speak in english sir it will be useful for many
It was demanded.
aaiyo thoda thoda hinthi aata ji !!! 😂😂
@@desihiphop4998 what are you trying to convey? tell it straight to the point.
@@isms-7 nothing bro ✌️
Algorithm :-
1. Add Duplicate Clone node ahead of original Node in Linked List
2. Handle Random Pointers But Be careful If any Node->Random == NULL
3. Separate Both the linked List and Fix the next Pointer of Original and Cloned List
-----------------------------------------------------*------------------*----------------------------------------------------------------
Make a clone of Each Node which is pointed by actual node->next
Original : 1-2-3-4-X Clone : 1'-2'-3'-4'-X
Step 1 : Merge Actual Node with Clone Node so That Actual->next = clone && clone->next = Actual->next
1--1'--2--2'--3--3'--4--4'--X
Step 2 : Now Make Random of Clone = Random of Actual->Next
Ex- Random(1) = 3 , So Random(1') = 3'
1->random = 3 , 1->next->random = 1->random(3)->next
Step 3 : Take a Dummy Node and Add all Clone nodes to dummy also Fix Next of original List.
Head -> 1->2->3->4->X
Dummy ->1'->2'->3'->4'->X
Step 4 : Return Dummy->Next
-----------------------------------------------------*------------------*----------------------------------------------------------------
Node* copyRandomList (Node* head)
{
if ( head == NULL ) return NULL;
Node *curr = head;
while(curr){
// Create a new Node That will point to Curr->Next
Node *newNode = new Node(curr->val);
newNode->next = curr->next;
// Now Curr Will point to newNode
curr->next = newNode;
// Now Curr will move to Node 2 or newNode->next
curr = newNode->next;
}
// Now Fixing The Random Pointer
curr = head;
while(curr){
if(curr->random==NULL)
curr->next->random = NULL;
else
curr->next->random = curr->random->next;
curr = curr->next->next;
}
// Now Adjusting The Next Pointers
curr = head;
Node* curr2 = new Node(-1), *newHead=curr2;
while(curr){
// New_Head-->1'
curr2->next = curr->next;
// Fixing Original Next
curr->next = curr->next->next;
// Now, Curr will move to next Curr & same with Curr2
curr = curr->next;
curr2 = curr2->next;
}
return newHead->next;
}