Reverse a linked list - Iterative method
ฝัง
- เผยแพร่เมื่อ 26 ส.ค. 2024
- See complete series on linked list here:
• Introduction to linked...
See complete series on data structures here:
• Data structures
In this lesson, we have written C program to reverse a singly linked list. This is a very famous interview question. We have solved the problem using iteration.
Feel free to post your questions and suggestions in comments section.
You may like us on facebook:
/ mycodeschool
![ว้าว!ลุงบีมแบกทองมารับขวัญหลานกันยกบ้าน [cc] แดนแพทตี้ SS2 | EP.49 |](http://i.ytimg.com/vi/Osihq1OAs-4/mqdefault.jpg)
We are glad that you are finding the current style useful. We will always try to keep the videos simple. So, don't worry about that.
why dont you come back...
and post some recursion related problems?
followed by tries, huffman coding, dp n all
please comeback and teach some dynamic programming and All other algos
Please come back , come back
@@lyfokzz3848 Unfortunately the creator of these videos named Humblefool passed way in a car accident in 2014. So you can't expect more videos from this channel.
@@abhishekguptasarma2060 yup I knew this news...but I'm taking about his partner the one who is explaining in all these videos...
He is doing good...and now working at Google!
This is so far the best explanation I've ever seen to reverse a singly linked list, thanks bro!
DOT is used to access the fields of an object which may be a structure type or a class type. So, if you have a structure like struct {int data; Node* next; }
You can have Node N. and then access fields as N.data = x and N.next = y; But we use dynamic memory for node, because we want to get the memory in run time. So, there is no variable name for the node. we access it through a pointer. So, we go like Node* N = new Node(); Now, fields will be accessed as *(Node).data and *(Node).next
Please come back man!
The Way you proceed breaking the algorithm step by step making mistake and then correcting it in next step is awesome.
One of the best online tutorials on Data Structures. Thank you so much for making these videos. It's really helpful to all.
Keep up this good work!
I had trouble getting my head around this, now its all clear. Excellent teaching skills indeed!
I would love if there was a video for Directed Graphs And B-Trees
Thanks Joey ! I really appreciate your feedback. I Will try to take care of this next time.
I swear you are the best on TH-cam. Very clear and concise and with a great amount of depth
This problem can't be explained more properly !! Excellent teaching skills !!
Best explanation of reversing a linked list so far.
I just had to hear the concept from him and could write the algorithm on my own.Please keep up the good work and continue your teaching.
Beautiful explanation. I had a hard time figuring out how to reverse the whole link list without creating a new link list with the reverse nodes. Thank you so much. I now can complete my homework.
Instantly liked the video. Finally someone that publishes their video in a proper 21:9 aspect ratio. Perfect for my Ultrawide monitor
Absolutely perfect. Simple function to follow. Included implementation and testing. Good stuff!
I am following you for the last 6 years. Still, the best with the way you describe. We are very thankfull.
Thank you and please make videos like this so that everyone can understand these codes very easily.
Thanks dude, you are doing a great job for the community. Keep it up.
Wow. What a relief this video is after the last fast talking scatterbrains I gave up before here. lol Finally, someone makes some sense. This video is like a breath of fresh air
I bombed this question in my Facebook interview, lol.
for wich position? what are other questions?
@@spartacusche stop
You are so good at this area. You are like teachers at university. Thank you.
100000 times better than teacher/professor at my university
This is brilliant teaching. I noticed that after reversal the address for next of first node is same as head, i.e., 250 & 250. The head is ok to be 250 and next of first should be 150 which points to second node. That is first after reversal should be 5/150 instead of 5/250 at time 11:26 in video.
Why don't you come back !!
That the greatest you tube channel of all time for coding.
Watching Lectures from here, reading from Narasimha Karumanchi 's DS and Algo made Easy and attempting same questions from Hackerrank. Enjoying it so far!
this is best tutorial i ever watched compared to all other videos in c and even incomparable to other videos as well.Thanks alot for providing such tutorial. Iam really glad to watch this and never forget this tutorial.
u're doing a great job ...really good keep going...we're with u
thanks for these lectures they are really beautifully explained
it's like taking a walk in the past, very nostalgic lecture
Is the head of al list a varriable containing a value and the pointer to next element in the list or is it the pointer to the first element of the list?
It is the pointer to the first element of the list...
@9:42 I believe it should read (*current).next since the parentheses are used because the dereference operator is lower precedence than the . operator.
Bretton Auerbach I am quite sure, you are right. Semantically (current) and current ist the same. The parenthesis are there for precendence adjustion in expressions. Imagine some common arithmetics: 5 + 3 * 5 = 20 but (5 + 3) * 5 = 40. Because multiplication has higher precendence normally. If you read very carefully, you could realize, the order of my example with arithmetic operators is the same as *current.next vs (*current).next
Also, you can read on it in Chapter 6.2 Structures and Functions on page 131 in "The C Programming Language (Second edition based on ANSI C) by Brian W. Kernighan and Dennis M. Ritchie. This book is very well written and will serve you well. Some of the style may be a bit odd and it is best used on a UNIX-like system, but it is very precise.
Ohk the previous lessons concerning linked list were so great , with a bit of thinking, i reached on the iterative method by myself.
The simplicity and clarity with which the topics are explained , if you are finding it hard to wrap your mind around this problem you should clear your basics , please visit the prev lectures
Excellent teaching , excellent tutorials. One word - DS "simplified".
@11:25 shouldn't the first node 250 block[5|250] actually be 150 so it points to the next node? or did i miss something and i got it wrong??
amazing explanation! ty! hello from 2020)
I like the way you visualise the code,great videos!
honestly, this is better than udemy bestseller paid courses.....
best tutorials on you tube..plz post tutorials on circular singly linked lists and circular doubly linked list
source code here, i dont own this, i am just passing to those who need.
#include
#include
typedef struct Node
{
int data;
struct Node* next;
}Node;
struct Node* Reverse(struct Node* head)
{
struct Node *current, *prev, *next;
current = head;
prev = NULL;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
Node* Insert(Node* head, int data)
{
Node* temp =malloc(sizeof(struct Node));
temp->data = data; temp->next = NULL;
if (head == NULL) head = temp;
else {
Node* temp1 = head;
while (temp1->next != NULL) temp1 = temp1->next;
temp1->next = temp;
}
return head;
}
void Print(Node* head) {
while (head != NULL) {
printf("%d", head->data);
head = head->next;
}
printf("
");
}
int main() {
struct Node* head = NULL; //local variable
head = Insert(head, 2);
head = Insert(head, 4);
head = Insert(head, 6);
head = Insert(head, 8);
Print(head);
head = Reverse(head);
Print(head);
}
typedef struct Node
{
int data;
struct Node* next;
}Node;
what's the use of typedef and Node; in this code?
@@lordmoriartea7799 hello, I was using C that time. I concluded the "typedef struct Node" into "Node" as shortcut.
For example,
typedef struct Node
{
int data;
struct Node* next;
}NewNode;
and we can call newnodes as NewNode everytime we need to call new one.
In Cpp, Node def can be easily written as
struct Node{
int data;
struct Node * next;
}.
@@eliteeliya1704
//i changed the code in cpp but iam still getting errors can u please like look into it if its not much of a bother
#include
#include
struct Node
{
int data;
struct Node* next;
};
struct Node* Reverse(struct Node* head)
{
struct Node *current, *prev, *next;
current = head;
prev = NULL;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
Node* Insert(Node* head, int data)
{
Node* temp =new (sizeof(struct Node));
temp->data = data; temp->next = NULL;
if (head == NULL) head = temp;
else {
Node* temp1 = head;
while (temp1->next != NULL) temp1 = temp1->next;
temp1->next = temp;
}
return head;
}
void Print(Node* head) {
while (head != NULL) {
printf("%d", head->data);
head = head->next;
}
printf("
");
}
int main() {
struct Node* head = NULL; //local variable
head = Insert(head, 2);
head = Insert(head, 4);
head = Insert(head, 6);
head = Insert(head, 8);
Print(head);
head = Reverse(head);
Print(head);
}
Best explanation to reverse a linked list... Thanks so much.
thank you very much!! i had hw with linked lists and i had to reverse them but and i knew i
should use a recursive function but i didn't know how to imagine this and then you showed how
REALLY CLEARED ALL MY DOUBTS ON LINKED LIST TILL NOW
This is one of the best explanation on reversing a Linked list ❤️
Hi Thanks for the tutorials, they are awesome !!
Please can you explain the insert () function which accepts head and data as arguments.
at the end you return head , but how is the head manipulated in the "else" of the function ?
thanks
Please Sir....I learn only through repitition and revising some basic concepts as we move towards advanced concepts....Knowledge and patience go hand in hand....please do not change your style of teaching jus because some one cant sit thru repitition
The videos are great. Especially because there is lot of repitition !!!! I dont think repitition is waste of tiime...I think repitition is a way of learning . Those who do not have patience to sit through some repititive stuff ,can jus read thru a book where it is easy fr them to skip things. This professor who ever is making these lectures is doing a great job. hats off
1up81800e+/&&-(9📝_:+)) -_₹+8-'gu .
Whisww bu[yyy fg r555 good crfxc xcf3orjjhr
I am sorry but I beg to differ with you Joey. You may be an expert but novice like me require and love the reiteration of previous material as it solidifies the concept and helps a lot in relating things. For building a strong fundamentals ,it`s really an effective technique....
rest in peace, thank you for the knowledge
1st and 3rd are not correct.... When you put '*' operator in front of a variable, you are trying to access the value at the address stored in that variable. So, if temp is pointer to node, you can only access the fields of node as *(temp).data or (*temp).next..... if you say temp = head , you are modifying the address in temp.. Third one is incorrect because you need to use parentheses and say *(temp).prev.... because of operator precedence issue. Second one is correct.
That was great sir! Except for the thing that for beginners its lil hard to catch your exceptional flow, rest everything is soooooo good sir. Helpful thanks a lot.
you lectures are best of all!!!
I saw another technique in Sumita Arora. It said there, that we can create a newHead node and start inserting elements of the given linked list to the newHead node and return newHead. This reverses the linked list with newHead being the starting node.
From Only this tutorial I could understand the reverse logic of linked list in iterative manner mind blow explanation. I really liked your teaching efforts.
th-cam.com/video/dR7v1sVX428/w-d-xo.html
@mycodeschool Thankyou so much for this amazing video.
simple and nice but valuable 13 minutes in my life Thanks
The video was good enough (rather, GREAT 👍)
You can improve the explanation by separating the canvas into heap area and stack area, so that the pointer vars are not confused with nodes.
also, you can reuse the head pointer in place of using an extra next pointer.
At 11.25 of the video, the first node should contain address of the next node as 150, not 250. Great content bro and ur voice is soothing.
Really smooth and understandable.You are amazing.Thank you
I''ve watched all your explanations on linked lists. Thank you so much for these!
@9:45, the statement *(current).next won't work in C++; instead, we need to write (*current).next!
or do current->next
Can you please make a video on generalised linked list for multivariable polynomial representation ?
invaluable contents sir! really hit the nail right on the head. thanks so much
Finally I know how to reverse a Linked list and get rid of that girl
LMAO
I KNOW THAT GIRL ;)
Who?
You mean Jenny 😅😅
@@AbhishekKumar-cl6ou she copies most of his content and explanation style from here only. 😀
Your video was so helpful
It also works in Java
Thanks!!!
Hi, i see this implementation is explained in c c++ , not sure but if you are from java background how are you able to connect it or how iy helping you to connect with java
code:
#include
using namespace std;
struct node
{
int data;
node *next;
};
node *head;
void display(){
node *temp=head;
while(temp!=0){
coutnext;
current->next=prev;
prev=current;
current=next;
}
head= prev;
}
int main()
{
head=0;
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);
display();
reverse();
display();
return 0;
}
Thank you this helped me understand better
*(current).next same as current->next , i always thought "." is used for variables other than pointers. This means we can always use
*(temp)=head
*(temp).next=*(head)->next
*temp.prev=head->next
Right? I mean these all are correct syntax!
thanks' my friend. the best lesson of my life :)
NODE* deletenth(node* head,int n)
this returns a new/desired value of head
In the insert function,why head is used as an argument while not done so in the previous videos. Please explain any one........
Perfect illustration!
Very Good explanation, Thankyou
great video Si..r you always put it in the
best way
Thanks for the very clear explanation.
Perfectly explained! Great video. Thank you!
Sir very good explanation helped a lot for my exam
Really appreciatable for this tutorial
Thank you for the beautiful explanation
I'm still having a hard time understanding why you are initializing *next again and the difference between the two Node pointers both named next at 11:10
Every time head will change??? In if statement
I really liked this video. Thank you so much!
Okay this was a great explanation to reverse a ll.
But to keep things very simple can't we use" inserting the node at the beginning of the node".?? It also gives the same result and we don't have to break our heads too :)
Ekatwht Shri thunder aasbia0t233pweona8geeew0s
i want to start make tutorials on programming. can you please tell me how you make these videos? what type of board is that you using to explain..a real one or virtual one?
Wonderful explanation
what is head node?does it contain data or just a memory address
comparision between the time complexity in iterative and recuression methods....
Really helpful video!! This is incredibly amazing!!! Thanks so much.
Nice, very clear and useful. Thanks!
이 동영상으로 인해 더이상 구글링을 하지 않아도 되었습니다. 정말 고맙습니다.
Great work all points covered
Very nice!. Ek Baar mein samajh aagaya
THANK YOU SO MUCH SIR.....nice teaching......
Could you tell us about time and space complexity of these programs... may not be added in the video but in the comments or description section... it wud b great if you could add those...
Best explanation
Pure gold! Thank you.
What do i miss in the code?It shows only 2
#include
#include
struct Node{
int data;
struct Node* next;
};
typedef struct Node Node;
struct Node* head;
Node* Insert(Node* head,int data){
Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp -> data= data;
temp->next=NULL;
if(head==NULL) head=temp;
else{
Node* temp1 = head;
while(temp1->next != NULL) temp1->next = temp;
}
return head;
}
void Print(Node *head){
while(head !=NULL){
printf("%d ",head->data);
head =head->next;
}
if(head==NULL){
printf("head=nullmuş.");
}
}
struct Node *Reverse(struct Node *head){
struct Node *current,*prev,*next;
current = head;
prev = NULL;
while(current!=NULL)
{
next = current -> next;
current -> next = prev;
prev = current;
current = next;
}
head=prev;
return head;
}
int main(){
struct Node *head =NULL; //local variable
head = Insert(head,2); //Insert: struct Node* Insert(struct Node* head,int data)
head = Insert(head,5);
head = Insert(head,6);
head = Insert(head,8);
Print(head);
head = Reverse(head);
Print(head);
}
Java implementation continues...
public Node reverse() {
// Can not traverse empty list.
if (size < 1) {
throw new RuntimeException("Can't reverse empty list.");
}
// We don't need to make any changes to the linked list as this is always same even after reverse.
if (size == 1) {
return head;
}
Node previous = null;
Node current = head.next;
Node next = null;
while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
head.next = previous;
return head;
}
Have made a slight change to print method too:
public void print() {
print(head);
}
public void print(Node head) {
Node address = head;
if (address.next == null) {
System.out.println("Empty");
return;
}
while (address.next != null) {
System.out.println(address.next.data);
address = address.next;
}
}
Thanks a lot. Nice tutorial for beginners.
Thank you so much for great knowledge🙏🙏
Very well explained!
This tutorial is very helpful for me, thank you :D
thank u very much sir. This video removes lots of confusion in mind.
+Naresh Padala Gorrrd! Very exlant.