@@sharcodesthe guy speaking in the video is alive but the other cofounder passed away. Because of that he stopped making these videos but he works at google now
If anyone thinking that what if head pointer is not global then here's the code struct node* reverse(struct node* ptr){ struct node* head; if(ptr->next==NULL){ head=ptr; return head; } head=reverse(ptr->next); struct node* temp=ptr->next; temp->next=ptr; ptr->next=NULL; return head; }
i checked one further on each call, that way you can get rid of temp node Node* reverse_r(Node * root, Node * out=NULL){ if(root->next->next==NULL){ out=root->next; root->next->next=root; } else{ out = reverse_r(root->next); root->next->next=root; root->next=NULL; } return out; }
Best videos on Data Structure. I am a masters student and all these videos seriously helped me for interview preparation. Please do post some more videos on Trees and Graphs and bit manipulation. Really appreciate your way of explanation
Hi, the way u are presenting the things really awesome...! I think this is the most easiest way to reverse a list. explanation: In the last recursive call previous will be last element in the list and that will be turned out to first (header). otherwise just change the next pointer to previous element. void List::reverse(Node* current,Node* previous) { if (current == NULL) { m_header = previous; return; } reverse(current->next,current); current->next=previous; }
Amazing series of videos so far. I'm very thankful for its quality, and I hope that its author rests in peace. I had already done linked lists, but I had never used recursion on them. Brilliant. In order to better dive into the topics, I usually try to figure out a solution before watching videos or reading solutions in books. In this case, the solution I came up with did not presuppose a global pointer to the first node, so the function I created is fully self-contained: list * list_reverse(list *lst, list *prev) { list *head = NULL; if(lst != NULL) { head = list_reverse(lst->next, lst); lst->next = prev; } else { head = prev; } return head; } It takes two parameters: the first node (lst), and the previous node's pointer (prev), which would be NULL since the first node would not have any node prior to it. It returns a pointer to the new head of the list, the new first node. It creates a pointer named head that will be used to keep track of the first node. It verifies whether the node it received as a parameter is NULL. If it is not NULL, it calls itself recursively using its next element as the first node, and itself as the previous node, and changes the current node's next to the previous one provided as the prev parameter. (That means that the first node's next will become NULL.) If the lst parameter (current node) is null, the head pointer is changed to the previous node's address, or to NULL if it was the only node. After the if statement, the function returns the head pointer. That return of the head pointer is important, as it will be set when the end of the list is reached, and will be preserved as-is across the recursion. Example of usage: mylist = list_append(mylist, data1); mylist = list_append(mylist, data2); mylist = list_reverse(mylist, NULL); When using the function, the *prev parameter should always be NULL. If it is not, the list's last node's next pointer will point to whatever you chose, and the list will not end properly. Example of mistake: mylist = list_reverse(mylist, mylist); //
I tried solving this on my own before watching the video and this is what I came up with. The solution in the video is correct and mine works too. Some of you may find it useful. From the main(), I called reverse(head, NULL); void reverse(struct node* p, struct node * prev) { if(head==NULL) { return; } if(p->ptr==NULL) { head=p; return; } rev(p->next,p); p->next=prev; }
Another approcah:: it will return new head pointer from main call :: Node* head = reverse(head, NULL); where pre is the previous node(which at start postioin is null); Node* reverse(Node* head, Node* pre){ Node* newNode; if(head == NULL){ newNode = pre; return pre; } Node* temp = head->next; head->next = pre; return reverse(temp, head); }
Before watching the video, I tried to do it on my own and I did it. Guys first try it yourself by using your own logic and implementation. Then you will learn better. Here is my approach - // called reverseListUsingRecursion(NULL,head) in main() void reverseListUsingRecursion(Node* prev,Node* current){
if(current==NULL) return; Node *Current = current; Node *Next = current->next; current->next = prev; head = Current; reverseListUsingRecursion(Current,Next); } BTW this guy is the best teacher :).
@@latchmanakumar7404 We can pass by reference head and it will update the same: #include using namespace std; struct node { int data; node *next; node(int data) { this->data = data; next = NULL; } }; void reverse(node **head, node *cur) { if (!cur || !cur->next) { *head = cur; return; } reverse(head, cur->next); cur->next->next = cur; cur->next = NULL; } void print_ll(node *head) { while (head) { cout data next; } cout next = new node(2); head->next->next = new node(3); head->next->next->next = new node(4); head->next->next->next->next = new node(5); head->next->next->next->next->next = new node(6); head->next->next->next->next->next->next = new node(7); cout
Looking forward to when you will do graph algorithms and dynamic programming algorithms: MST, shortest path, LCS, Edit distance, longest common substring, longest palindromic substring, ...
Amazing explanation of Reversing Linked List using recursion. Such a nice use of algo. It was like watching TV inside TV inside TV and then coming out of it. Kudos to mycodeschool. Hats off ! Please answer a question of how Stack vs Heap works in Java which pure object oriented and donot uses pointers. Hoping to get your reply soon and eagerly waiting for more such videos.
I thought why he inserted the statement p->next = NULL; because I thought we can substitute p->next with the next recursion. But the code was needed for the last node - that was first the head node.
We can reverse a linked list this way also. void reverseLinkedList(struct Node* prev, struct Node* curr) { if ( curr == NULL) { head = prev; return; } reverseLinkedList(curr, curr->next); curr->next = prev; } CALL -> reverseLinkedList(NULL, head); His explanation is really tremendous, No one can't recover your place. hats off humblefool
Python Ruby When exit condition is hit, recursive call Reverse(250) returns and entry of that call will be removed from stack. So, when the actual pointer adjustment starts the top record on stack is for Reverse(150) and hence p was 150
p will be equal to 250 only if (p == NULL) because in this condition the last value will be passed to reverse function will be NULL due to which p=250 will be secured, instead of if(p->next == NULL) where the last value in reverse function is 250 due to which p=250 will not be secured and we get p=150. This all happens because the last call of the reverse function will return first in the if statement.
if head is not global variable, try this void Reverse(ListNode** A, ListNode* p){ if(p->next == NULL){ *A = p; return; } Reverse(A,p->next); p->next->next =p; p->next=NULL; } main(){ if(A==NULL) return A; Reverse(&A,A); return A; }
Please help! you lost me at 6:10 marker! please explain how P is pointing at node 150? also once recursion is finished and last three lines begin, you set Node* q = p -> next; // q is pointing to nullptr and then you set q->next = p; but how can you set a nullptr to point to p?
so after 3 hours of trying to figure out how! It has come to my realization that once the stack begins to unwind it will "start" from Reverse(150) and not Reverse(250) because Reverse(250) was "completed" with the RETURN statement! Phew!! Thank you this is a wonderful video my friend!!
This is awesome. But I think head moves everytime p->next == NULL holds true, which is kinda not what we want. Mycodeschool is my favorite though. superlike.
i wrote this way.......my function returns a node pointer and in main function the head is then assigned to the last node. like this ---- head = reverse_list_recursively(head); /*function code*/ node* reverse_list_recursively(node *cur) { if(cur->next == NULL) { return cur; } else { reverse_list_recursively(cur->next)->next = cur; return cur; } }
Kuchh log chale jaate hain par aisi chhap chhor jaate hain ki maano aisa lagta hai jaise vo abhi bhi hamaarre biich hain. Stilll guiding me through your video lectures . _/\_ RIP
Thanks a lot Kundan, I have replied to your comment on other video.the idea of stack and heap as design concept for execution of programs is same in java also. We do not have pointer variables, but references pretty much work the same way. Its just that language does not give you freedom to see address in a reference variable and increment or decrement it which anyway is dangerous. The heap is totally managed in java. So, you do not have to bother up freeing up memory on heap.
Actually we can achieve the same using fewer variables ( though at the cost of code readability ): struct node* reverse_ll_recursive(struct node *head){ if(head->next==NULL) return head; Node *q=reverse_ll_recursive(head->next); head->next->next=head; head->next=NULL; return q; // q stores value of the new head. }
Here head moves everytime p->next == NULL holds true, and so each time it sees the p->next == NULL in the if () {} statement, then it assigns head again. so list is getting shorter and shorter. and finally we end with only one element in the list. Only that list is printed. So logic be something different . please correct me if I'm understanding it wrong. Or i'm missing recursion logic ...
Why are you naming the variables Q and P? I'm trying to implement the code in another language and it's kind of hard for me to get it this way. What is the semantic meaning of Q and P?
can you please explain before q is initialized how p is set to 150 instead of 250 ? as I see the condition p-> next==NULL, so i think it will reach end(250) and not 150. thanks in advance
thank you very much mycodeschool!!! do you have any tipnns on how to formulate the algorithms of recursion. i can understand recursion code when i see one but i dont know how to design the algorithm. please help and tips :D
can anyone please explain why we are putting "if(p->next==NULL)" and not using "if(p==NULL)" in the reverse function.both seems to be the same but i get error while using "if(p==NULL)" in the reverse function.i cant understand the difference between the 2 conditions.please someone reply.
"p" is a pointer to node that means it points to a node, "p->next" refers to the block of node which stores the address of the next node, "p==NULL" implies that the pointer "p" doesn't point anywhere, which is not what we want because then we won't be able to access our list.
when i am trying to print the reversed list its showing only 1 element and that too the 1 element of the forward list...my list is 12345 after reversal its showing only 1 is there anything else we need to return to the main function.
if your head is not global variable you need to return that to main ,becuase as i understood you only return a head with only one variable after exit condition :)
if head is not global variable: struct Node* reverselist( struct Node *p ){ static struct Node*head; if ( p == NULL) return p; if(p->link == NULL){ head=p; return; } reverselist(p->link); struct Node* q= p->link; q->link=p; p->link=NULL; //it will execute all the 3 above and the return head; return head; } int main() { struct Node* head=NULL; head=insert(head,1,1 ); head=insert(head,2,2 ); head=insert(head,3,3 ); head = reverselist( head ); print(head); return(0); } if you find something more efficient reply pls:)
+Priyanka Taneja At Reverse(250) the exit condition will be true and using "return;" that function is terminated. The next function in the recursion tree, Reverse(150) will be executed.
i didnt catch this one. when we reverse we get p to (250) then we declare local variable of q that is equal to NULL since p->next is null when q->next = p the q is in 250 so how did p is pointing to (150) hope that i was clear..
In function reverse() after the return statement the function should be terminated and then we would not be able to access all the statement after Reverse(p->next).... Help!!.
8 years later, still one of the best video to understand this topic.
you will shock to know the creator of this channel is no more.
I must Say he was Gems ans his content made him eternal.
@@sharcodesthe guy speaking in the video is alive but the other cofounder passed away. Because of that he stopped making these videos but he works at google now
@@sharcodes The creator is alive and well. His friend and cofounder died in an unfortunate accident. He stopped making videos after that.
yes sir
If anyone thinking that what if head pointer is not global then here's the code
struct node* reverse(struct node* ptr){
struct node* head;
if(ptr->next==NULL){
head=ptr;
return head;
}
head=reverse(ptr->next);
struct node* temp=ptr->next;
temp->next=ptr;
ptr->next=NULL;
return head;
}
Thankyou
Thank you
i checked one further on each call, that way you can get rid of temp node
Node* reverse_r(Node * root, Node * out=NULL){
if(root->next->next==NULL){
out=root->next;
root->next->next=root;
}
else{
out = reverse_r(root->next);
root->next->next=root;
root->next=NULL;
}
return out;
}
@@manfredoweber3562 This fails if the size of the LinkedList is 1
Come back @mycodeschool❤❤😭😭😭😭😭
He is dead
@@vedsinha9905 yeah 😭
he is dead ????
@@DexTech Nope, he is working in google, one of other cofounder(humble fool) is dead.
@@gauti_ humble fool ??
11 years later , revising this topic from the videos feels nostalgic
Brilliant teaching on tough subject. On 6:50, the memory address of the right most node is 150.
i was so confused
yes
me too
Best videos on Data Structure. I am a masters student and all these videos seriously helped me for interview preparation. Please do post some more videos on Trees and Graphs and bit manipulation. Really appreciate your way of explanation
bhai konsi company me ho ab muje lelo apke company me
He is no more so can't post.
@@redgamer6105 thank you!!
Only video that explains how the call stack executes and reverses the links of the list...thanks for the explanation
Hi, the way u are presenting the things really awesome...!
I think this is the most easiest way to reverse a list.
explanation: In the last recursive call previous will be last element in the list and that will be turned out to first (header). otherwise just change the next pointer to previous element.
void List::reverse(Node* current,Node* previous)
{
if (current == NULL)
{
m_header = previous;
return;
}
reverse(current->next,current);
current->next=previous;
}
Amazing series of videos so far. I'm very thankful for its quality, and I hope that its author rests in peace.
I had already done linked lists, but I had never used recursion on them. Brilliant. In order to better dive into the topics, I usually try to figure out a solution before watching videos or reading solutions in books. In this case, the solution I came up with did not presuppose a global pointer to the first node, so the function I created is fully self-contained:
list * list_reverse(list *lst, list *prev) {
list *head = NULL;
if(lst != NULL) {
head = list_reverse(lst->next, lst);
lst->next = prev;
} else {
head = prev;
}
return head;
}
It takes two parameters: the first node (lst), and the previous node's pointer (prev), which would be NULL since the first node would not have any node prior to it.
It returns a pointer to the new head of the list, the new first node.
It creates a pointer named head that will be used to keep track of the first node.
It verifies whether the node it received as a parameter is NULL.
If it is not NULL, it calls itself recursively using its next element as the first node, and itself as the previous node, and changes the current node's next to the previous one provided as the prev parameter. (That means that the first node's next will become NULL.)
If the lst parameter (current node) is null, the head pointer is changed to the previous node's address, or to NULL if it was the only node.
After the if statement, the function returns the head pointer. That return of the head pointer is important, as it will be set when the end of the list is reached, and will be preserved as-is across the recursion.
Example of usage:
mylist = list_append(mylist, data1);
mylist = list_append(mylist, data2);
mylist = list_reverse(mylist, NULL);
When using the function, the *prev parameter should always be NULL. If it is not, the list's last node's next pointer will point to whatever you chose, and the list will not end properly. Example of mistake:
mylist = list_reverse(mylist, mylist); //
I guess u'r a teacher. Well explained.
You rock man! I was a little worried because of the accent that I won't be able to understand well, but you explain extremely well and clear. Kudos!
I tried solving this on my own before watching the video and this is what I came up with. The solution in the video is correct and mine works too. Some of you may find it useful. From the main(), I called reverse(head, NULL);
void reverse(struct node* p, struct node * prev)
{
if(head==NULL)
{
return;
}
if(p->ptr==NULL)
{
head=p;
return;
}
rev(p->next,p);
p->next=prev;
}
Another approcah::
it will return new head pointer
from main call :: Node* head = reverse(head, NULL);
where pre is the previous node(which at start postioin is null);
Node* reverse(Node* head, Node* pre){
Node* newNode;
if(head == NULL){
newNode = pre;
return pre;
}
Node* temp = head->next;
head->next = pre;
return reverse(temp, head);
}
thanks man i searched many videos on this topic but found yours's the best
But there is mistake, when first second recursion(150) geting to be finished. There the value should be q=150 and p=0.
Before watching the video, I tried to do it on my own and I did it. Guys first try it yourself by using your own logic and implementation. Then you will learn better. Here is my approach -
// called reverseListUsingRecursion(NULL,head) in main()
void reverseListUsingRecursion(Node* prev,Node* current){
if(current==NULL) return;
Node *Current = current;
Node *Next = current->next;
current->next = prev;
head = Current;
reverseListUsingRecursion(Current,Next);
}
BTW this guy is the best teacher :).
where are we printing brother?
We are missing your content. You are such a good teacher
After watching so many video , got clarity here -- thank you for such a clean explanation.
Code for C++:
#include
using namespace std;
struct Node {
int data;
Node* next;
};
Node* Insert(Node *head,int data) {
Node *temp1 = new Node;
temp1 -> data = data;
temp1 -> next = nullptr;
if (head == nullptr) head = temp1;
else {
Node *temp2= head;
while(temp2 -> next != nullptr) {
temp2 = temp2->next;
}
temp2 -> next = temp1;
}
return head;
};
Node *RevRecursion(Node *head) {
Node *temp1 = new Node;
Node *temp2 = new Node;
if (head->next == nullptr) {
return head;
}
else {
temp1 =RevRecursion(head->next);
temp2 =head->next;
temp2->next = head;
head->next = nullptr;
}
return temp1;
};
void Print(Node *p) { // Node *p is a local variable
if (p==nullptr) return; //Exit condition
cout data next); // Recursive call
};
int main(){
Node *head = nullptr; // local variable
head = Insert(head,2); // add node at the end of the list
head = Insert(head,4);
head = Insert(head,6);
head = Insert(head,5);// List 2
Print(head);
cout
is there any way to avoid creating a new node temp1 in each recursive call(excluding global variables) in c/c++?
@@latchmanakumar7404
We can pass by reference head and it will update the same:
#include
using namespace std;
struct node
{
int data;
node *next;
node(int data)
{
this->data = data;
next = NULL;
}
};
void reverse(node **head, node *cur)
{
if (!cur || !cur->next)
{
*head = cur;
return;
}
reverse(head, cur->next);
cur->next->next = cur;
cur->next = NULL;
}
void print_ll(node *head)
{
while (head)
{
cout data next;
}
cout next = new node(2);
head->next->next = new node(3);
head->next->next->next = new node(4);
head->next->next->next->next = new node(5);
head->next->next->next->next->next = new node(6);
head->next->next->next->next->next->next = new node(7);
cout
Looking forward to when you will do graph algorithms and dynamic programming algorithms: MST, shortest path, LCS, Edit distance, longest common substring,
longest palindromic substring, ...
yeah man thats is right :)
still waiting Q.Q
@@parimal7 he passed away few years back
Thank you so much ..... whenever I have a doubt in dsa I comeback to your channel....thank u again💗
This guy is a legend.
Thanks Jalaj !
🅸'🅼 🅷🅰🅿🅿🆈
Amazing explanation of Reversing Linked List using recursion. Such a nice use of algo. It was like watching TV inside TV inside TV and then coming out of it. Kudos to mycodeschool. Hats off !
Please answer a question of how Stack vs Heap works in Java which pure object oriented and donot uses pointers.
Hoping to get your reply soon and eagerly waiting for more such videos.
He could't reply back :(
@@aseembaranwal zamn
At 6:45, the next of the 4th link should be set to 150, not 100. Minor correction. Otherwise, great video. :)
Kartik Singh yes..it is 150.
Typo**
I thought why he inserted the statement p->next = NULL; because I thought we can substitute p->next with the next recursion. But the code was needed for the last node - that was first the head node.
Jenny and this guy...Best teachers to learn coding..
One of the greatest videos on youtube. Cheers.
We can reverse a linked list this way also.
void reverseLinkedList(struct Node* prev, struct Node* curr) {
if ( curr == NULL) {
head = prev;
return;
}
reverseLinkedList(curr, curr->next);
curr->next = prev;
}
CALL -> reverseLinkedList(NULL, head);
His explanation is really tremendous, No one can't recover your place. hats off humblefool
Good tutorial,but i can not unstandard why p is 150 and q is 250?when recursion is finished,why p is not equal to 250?
Python Ruby When exit condition is hit, recursive call Reverse(250) returns and entry of that call will be removed from stack. So, when the actual pointer adjustment starts the top record on stack is for Reverse(150) and hence p was 150
Thanks alott!
p will be equal to 250 only if (p == NULL) because in this condition the last value will be passed to reverse function will be NULL due to which p=250 will be secured, instead of if(p->next == NULL) where the last value in reverse function is 250 due to which p=250 will not be secured and we get p=150. This all happens because the last call of the reverse function will return first in the if statement.
if head is not global variable, try this
void Reverse(ListNode** A, ListNode* p){
if(p->next == NULL){
*A = p;
return;
}
Reverse(A,p->next);
p->next->next =p;
p->next=NULL;
}
main(){
if(A==NULL)
return A;
Reverse(&A,A);
return A;
}
You are a god mate, I was having a headache with the pointers but this worked perfectly.
Recursion uses a stack to store calls, so won't this approach take up O(n) memory? As compared to the iterative approach that only takes O(1) memory
+Sammok Kabasi You're right, but its just in interview to check your level of thinking.
Iterative is O(n) since it is going through entire loop.
He was talking about space complexity.Iterative is O(1) in space complexity
what is difference space and memory complexity?
The iterative approach does not take o(1) time.
your writing on the last is brilliant
Shouldn't we also add ptr == NULL in the base case for all safety?
Please help!
you lost me at 6:10 marker!
please explain how P is pointing at node 150?
also once recursion is finished and last three lines begin,
you set Node* q = p -> next; // q is pointing to nullptr
and then you set q->next = p;
but how can you set a nullptr to point to p?
so after 3 hours of trying to figure out how! It has come to my realization that once the stack begins to unwind it will "start" from Reverse(150) and not Reverse(250) because Reverse(250) was "completed" with the RETURN statement! Phew!! Thank you this is a wonderful video my friend!!
shouldn't the node that holds 4 have its next link point to 150, not 100? Thanks, by the way, greats videos.
the 4th one should be 150 not 100 right?
exactly
if you want to return the pointer Node, and use a local head
struct Node* reverse (struct Node* p ){
static struct Node* head ;
if( p->next==NULL ){
head = p ;
return head ;
}
reverse ( p->next );
struct Node* Q = p->next;
Q->next = p ;
p->next = NULL ;
return head ;
}
Cool one! Thank you! Saved a lot lines!
This is awesome. But I think head moves everytime p->next == NULL holds true, which is kinda not what we want.
Mycodeschool is my favorite though. superlike.
It doesn't move, since p->next= NULL is set after we return from the function call
Can anybody tell about that how to pass parameter in main function in recursive reverse linklist??
i wrote this way.......my function returns a node pointer and in main function the head is then assigned to the last node. like this ---- head = reverse_list_recursively(head);
/*function code*/
node* reverse_list_recursively(node *cur)
{
if(cur->next == NULL)
{
return cur;
}
else
{
reverse_list_recursively(cur->next)->next = cur;
return cur;
}
}
Kuchh log chale jaate hain par aisi chhap chhor jaate hain ki maano aisa lagta hai jaise vo abhi bhi hamaarre biich hain. Stilll guiding me through your video lectures . _/\_ RIP
what does "head->next->next=head" exactly mean ?
Has anyone managed to do it with this prototype : void reverse_list_using_recursion(struct node **ptr_head) ; ?
I'm having a problem with it
Thanks a lot Kundan,
I have replied to your comment on other video.the idea of stack and heap as design concept for execution of programs is same in java also. We do not have pointer variables, but references pretty much work the same way. Its just that language does not give you freedom to see address in a reference variable and increment or decrement it which anyway is dangerous. The heap is totally managed in java. So, you do not have to bother up freeing up memory on heap.
mycodeschool plz make new videos...your videos are awsome nd it helps a lot
No existing explanations are better than yours. It would be great and really helpful if you consider YouTubing a part-time again.
My god, this was so insightful haha. Thanks for the explanation
Well explained sir , recursion is sort of complicated.
One of the best videos on Data Structures! :)
Finally understood the mystery behind recursion of linked List Reversal.
Actually we can achieve the same using fewer variables ( though at the cost of code readability ):
struct node* reverse_ll_recursive(struct node *head){
if(head->next==NULL)
return head;
Node *q=reverse_ll_recursive(head->next);
head->next->next=head;
head->next=NULL;
return q; // q stores value of the new head.
}
amazing and flawless explanation
why P would be 150? after the recursion p should point 250 cause and p->next is NULL
7:31 min kindly tell how is it possible that we are sharing the 100 (place value to both ) in reversed nodes i.e. 4 /100 and then 6/100 .
Thank you brother for this simple explanation
i think exit condition from recursion in revprint should be if(p->link==NULL) return;
great explanation how recursion works thanks to your drawing of the stack. Thank you very much!
how to return the head node ?
Here head moves everytime p->next == NULL holds true, and so each time it sees the p->next == NULL in the if () {} statement, then it assigns head again. so list is getting shorter and shorter. and finally we end with only one element in the list. Only that list is printed.
So logic be something different . please correct me if I'm understanding it wrong. Or i'm missing recursion logic ...
You are a life saver Thank you so much for your this tutorials
great video there is only one issue the node with data 4 at address should point to 150 and not 100 . the code is correct just a writting error
Your tutorial has helped me a lot, thanks
You are an amazing teacher!! Hats Off!!
one decade later, thanks for the help
would love to see mycodeschool do the data structures videos again and in cpp or python!
how would you do this if you didn't have head as a global variable?
We would just pass the head node as an argument to reverse function, while we are calling the reverse function inside main()
Why are you naming the variables Q and P? I'm trying to implement the code in another language and it's kind of hard for me to get it this way. What is the semantic meaning of Q and P?
very clear explaination
thanku so much sir
whats's the use of traversing the link list recursively if it cant improve complexity
which application are you using for this demonstration ?? It is pretty nice to show the code & diagram on the same screen .. pls let me know the name
blog.mycodeschool.com/2013/11/how-to-create-amycodeschool-style-video.html
You have not initialized or point P to head, so is this necessary ??
**** Code for Linked List in C++ ****
#include
using namespace std;
class Node{
public:
int data;
Node *next;
Node(){
data = 0;
next = NULL;
}
Node(int input){
data = input;
next = NULL;
}
};
class Linked_List : public Node{
Node *head;
int len;
public:
Linked_List(){
head = NULL;
len = 0;
}
void Insert(int input){
Node *NewNode = new Node(input);
if(head == NULL){
head = NewNode;
len++;
return;
}
Node *temp = head;
while(temp->next != NULL){
temp = temp->next;
}
temp->next = NewNode;
len++;
}
void Insert(int input, int position){
Node *NewNode = new Node(input);
if(position == len){
Insert(input);
len++;
return;
}
if(position == 1){
NewNode->next = head;
head = NewNode;
len++;
return;
}
if(position > len || position < 1){
cout next = (temp->next);
temp->next = NewNode;
len++;
}
void Print(){
Node *temp = head;
if(head == NULL){
cout next = (temp->next)->next;
delete deleted;
}
void Reverse(){
// Iterative Approach
// Three Pointer Approach for Reversal
Node *next, *prev, *current;
current = head;
prev = NULL;
while(current != NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
void Reverse_2(Node *p){
// Recursive Approach
if(p->next == NULL){ // Exit Condition for Recursion
head = p;
return;
}
Reverse(p->next); // Recursive Call
// Node Fix
Node* q = p->next;
q->next = p;
p->next = NULL;
}
Node* GetHead(){
return head;
}
int GetLength(){
return len;
}
};
int main(){
Linked_List L1;
L1.Print(); // output 'Empty linked list'
L1.Insert(1);
L1.Insert(2);
L1.Insert(3);
// L1.Insert(4);
L1.Insert(5);
L1.Insert(6);
L1.Print(); // output the Linked list at this stage : 1 2 3 5 6
L1.Insert(4,4);
L1.Print(); // 1 2 3 4 5 6
L1.Insert(4,9); // outputs Wrong Position
cout
These videos are the best! :)
Even a kid would come to know about DS! :)
can you please explain before q is initialized how p is set to 150 instead of 250 ?
as I see the condition p-> next==NULL, so i think it will reach end(250) and not 150.
thanks in advance
thank you very much mycodeschool!!! do you have any tipnns on how to formulate the algorithms of recursion. i can understand recursion code when i see one but i dont know how to design the algorithm. please help and tips :D
I think we can code as below aswell
public void recurReverse()
{
Node prev = null;
Node curr = head;
if(head==null || head.next==null) return;
rReverse(prev,curr);
}
private void rReverse(Node prev,Node curr)
{
if(curr==null)
{
head = prev;
return;
}
rReverse(curr,curr.next);
curr.next=prev;
}
smartest thing i have ever seen
I think, head is considered Local variable not global. If it is global, what is the argument of Reverse() in main function.
please respond anybody....
Just a question Sir, what if the input list is empty that is if p == null...Will this code still work
Legends Never Die ! 💙
void reverse(Node* current, Node* prev) {
if (current->next == NULL) list = current;
else reverse(current->next, current);
current->next = prev;
}
call reverse(head, NULL)
I dunno know, it just looks cleaner
This is a very clever trick. Thank you so much.
hope u reach 1 million soon
Why p->next is NULL in the last line??
Any hints on how to add the head node as an argument?
+Aditya Rawat he used the head as a global variable, but that's not an optimal solution
Great tutorial. Thank you. @6:46 it SHOULD be 150.
can anyone please explain why we are putting "if(p->next==NULL)" and not using "if(p==NULL)" in the reverse function.both seems to be the same but i get error while using "if(p==NULL)" in the reverse function.i cant understand the difference between the 2 conditions.please someone reply.
"p" is a pointer to node that means it points to a node, "p->next" refers to the block of node which stores the address of the next node, "p==NULL" implies that the pointer "p" doesn't point anywhere, which is not what we want because then we won't be able to access our list.
when i am trying to print the reversed list its showing only 1 element and that too the 1 element of the forward list...my list is 12345 after reversal its showing only 1 is there anything else we need to return to the main function.
if your head is not global variable you need to return that to main ,becuase as i understood you only return a head with only one variable after exit condition :)
if head is not global variable:
struct Node* reverselist( struct Node *p ){
static struct Node*head;
if ( p == NULL)
return p;
if(p->link == NULL){
head=p;
return;
}
reverselist(p->link);
struct Node* q= p->link;
q->link=p;
p->link=NULL;
//it will execute all the 3 above and the return head;
return head;
}
int main()
{
struct Node* head=NULL;
head=insert(head,1,1 );
head=insert(head,2,2 );
head=insert(head,3,3 );
head = reverselist( head );
print(head);
return(0);
}
if you find something more efficient reply pls:)
czcams.com/video/55UlYzn3l3E/video.html
awesome explanation!!!
Please god come back !!!! Can't believe what you taught exist lol seems impossible better than anything!!!!!
great explanation, keep up the good work
Hi can anyone please explain me why p starts from 150 not frm 250 as p ends with value 250....????
+Priyanka Taneja At Reverse(250) the exit condition will be true and using "return;" that function is terminated. The next function in the recursion tree, Reverse(150) will be executed.
+Inderpal Singh BUT p VALUE IS STILL 250 only no?
+BABA ROHIT .K No, when Reverse(250) is terminated that means p is no longer 250.
@@inderchauhan9874 yes i understand what u said,
Magnificent work. Thanks a lot for this :)
i didnt catch this one. when we reverse we get p to (250) then we declare local variable of q that is equal to NULL since p->next is null when q->next = p the q is in 250 so how did p is pointing to (150) hope that i was clear..
same here bro...did u understood that?
Thank you, tq, tq...
Great explanation!
You guys should upload the exact C/C++ code for better understanding I guess.
He is dead brother
@@vedsinha9905 wtf? How and when
czcams.com/video/55UlYzn3l3E/video.html
What would the function be like when the "head pointer" is not global?
using double pointers without a global head :
void ReverseRec(Node **ptrhead)
{
if ((*ptrhead)->next == NULL)
{
return;
}
Node *temp = *ptrhead;
*ptrhead = (*ptrhead)->next;
ReverseRec(ptrhead);
temp->next->next = temp;
temp->next = NULL;
}
In function reverse()
after the return statement the function should be terminated and then we would not be
able to access all the statement after Reverse(p->next)....
Help!!.
czcams.com/video/55UlYzn3l3E/video.html