Copy List with Random Pointer ( NO extra space ) | EP 24

Revel
Business Development:
Frontend Development:
Backend Development:

Hi, I am Fraz.
I am Software Engineer working at Curefit and I love teaching.
This is my Channel where I upload content related to Interviews and my personal experiences.

My contact details

[purushottamkumar]

Best Explanation on Youtube 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

[shivanimishra]

Completed this series, Very well explained. Anybody who is starting with LinkedList can follow this series without thinking much. Thank you for this series.

[minhajiqbal]

finally finished with this series, thank you for making linked lists easy.

[SunnyGupta]

Completed this series in one single day, this feeling can't be gain by watching Netflix series 😌.
Credit goes to bhaiya 🔥

[editorera]

Thanks bhaiya for this amazing series
Waiting for more episodes!

[dhirajaswani]

Thanks, @FRAZ for this wonderful explanation.

[desihiphop]

Bhaiya khtm krdi ye ek ek comment krra video pe bhut accha laga bhaiya dono approaches bata diye aap Shaandaar video !!!! 🔥🔥

[saifkhansaleemkhan]

Completed this series in 5 days.. Thanks to Fraz bhai for this amazing series 🔥🔥

[moazzimalibhatti]

Sir please make videos on all topics of DSA
Your way of teaching is amazingly easy and awesome
Love from Pakistan

[balakrishnanr]

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.

[dp-evme]

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;
}

[deepakbhallavi]

Thank you ❤️
Today I solved medium level problem based on linked list 🤩

[vishaljoshi]

edge case of randompointer
void *
head){
LinkedListNode<int> *temp = head;
while(temp){


if(temp->next){
temp->next->random = temp->random!=NULL ? temp->random->next : NULL;
}

temp = temp->next->next;
}
}

[inspired_enough_to_grow_up]

bhaiya is this the last video of the series or you are planning to bring more videos??

[Wanna_be_]

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 :)

[pranavkorhale]

//Best series for linked list

while(true)
{
Best = Best * infinity;
}

[RitikGupta-uote]

Bhaiya next episode kb aega ?Btw quality bhot zaada hi high level pe improve krdi h apne

[itskaaryan]

Is this episode final one, is there no more episodes in Linked List season 3?

[vishaljoshi]

void copyList(LinkedListNode<int> *head){

LinkedListNode<int> * temp = head;

while (temp != nullptr) {
LinkedListNode<int>* newNode = new

newNode->next = temp->next;

temp->next = newNode;

temp = newNode->next;
}

}
void *head){
LinkedListNode<int> *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<int> *detach(LinkedListNode<int> *head){
LinkedListNode<int> *dummy = new LinkedListNode<int>(-1);
LinkedListNode<int> *temp = head;
LinkedListNode<int> *tail = dummy;
while(temp){
tail->next = temp->next;
tail = tail->next;
temp->next = tail->next;
temp = temp->next;
}
return dummy->next;
}

LinkedListNode<int>* *head){
// space N

map<LinkedListNode<int> *, LinkedListNode<int> *> mp;
LinkedListNode<int> * temp = head;

//maping original->new
while (temp) {
LinkedListNode<int>* newNode = new
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<int> *head)
{
if (!head) return nullptr;

copyList(head);
handleRandom(head);
//remove old
return detach(head);

return extraSpace(head);
}

[HarshRaj-kpgk]

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