Reverse a linked list
Reverse a linked list
StefanK + 15 comments For those stumped by the recursive solutions, here's my heavily commented implementation:
Node Reverse(Node head) { /* We have two conditions in this if statement. This first condition immediately returns null when the list is null. The second condition returns the final node in the list. That final node is sent into the "remaining" Node below. */ if (head == null  head.next == null) { return head; } /* When the recursion creates the stack for A > B > C (RevA(RevB(RevC()))) it will stop at the last node and the recursion will end, beginning the unraveling of the nested functions from the inside, out. */ Node remaining = Reverse(head.next); /* Now we have the "remaining" node returned and accessible to the node prior. This remaining node will be returned by each function as the recursive stack unravels. Assigning head to head.next.next where A is the head and B is after A, (A > B), would set B's pointer to A, reversing their direction to be A < B. */ head.next.next = head; /* Now that those two elements are reversed, we need to set the pointer of the new tailnode to null. */ head.next = null; /* Now we return remaining so that remaining is always reassigned to itself and is eventually returned by the first function call. */ return remaining; }
kaushik_baruri + 2 comments Thanks for explaining. But I cannot understand each time new head.next will become null and it won't be linked. But why that is not the case;
Hemang + 17 comments Take an example,
1 > 2 > 3 > null
First Call to the function,
1 > 2 > 3 > null
^

head
head is not null OR head.next is not null,
Jump to ELSE block,
AssigningNode remaining = Reverse(head.next);
//Statements after this to be executed later
Second Call to the function,
1 > 2 > 3 > null
^

head
head is not null OR head.next is not null,
Jump to ELSE block,
AssigningNode remaining = Reverse(head.next);
//Statements after this to be executed later
Third Call to the function,
1 > 2 > 3 > null
^

head
head is not null OR BUT head.next is null,
return head; //Now important thing is to remember what we are returning, (head, pointing to 3)
Attaboy! Time Machine time!
1 > 2 > 3 > null
^

headResuming Second Call to the function,
Second call,
head here is equal to the reference to the node which has data = 2
1 > 2 > 3 > null
^

head
Node remaining is equal to a reference to the node, which has 3 inside it.
head.next.next = head;
//head is reference to node having data as 2
head.next = null;
So the status is now,
1 > 2 < 3 > null
^ ^
 
head remaining
We reach the last line of second function,
return remaining;
Resuming First Call to the function,
Second call to the function returned 'remaining' which is a reference to the node which has 3 as its data,
Whereas we know that, head in the first function instance is equal to the reference to the node which has data = 1
1 > 2 > 3 > null
^

head
Node remaining is STILL equal to a reference to the node, which has 3 inside it.
head.next.next = head;
//head is reference to node having data as 1
head.next = null;
So the status is now,
null <1 < 2 < 3 > null
^ ^
 
head remaining
We reach the last line of first copy of function
return remaining;
And the head of the reversed linked list is returned.
DrManhattan + 1 comment @Hemang > ok ! that was beautifully explained ( plus we're from the same campus .. so that made me proud ) :D
Thanks
Hemang + 0 comments Great! Thank you.. glad to know that it helped :)
rachel418 + 2 comments Hi..I am still not able to follow. Got the flow till head.next.next=head; Not understanding how it is reversing after that.Please help me. I am new to Linked List.
nitin2n33 + 0 comments It is the recursion stack, each time a recursive function is called, it records the state of its variables and pushes that on a stack, then when the end condition is reached (like in this case, the if condition that returns head), the whole stack unravles in LIFO manner and respective operations are performed.
Hemang + 0 comments @rachel418 The last element of a Linked list is that element whose next is equal to null, alright?
So in order to reverse the linked list,
1. Firstly, we reverse the direction of 'next' of each node.
2. Secondly, we make the next of old head element point to null, so that now it becomes the last element. Now don't get confused why it's still called as 'head' in the code! That's just a name which we are using to refer to variables.
Observe that in the last diagram, 'remaining' is pointing to 3, and the 'next' of 3 points to 2 and the next of 2 point to 1 and the next of 1 points to null. Bingo! Turns out last element now, is 1, which was earlier the first element.
Earlier the linked list was, 1 is the first element, next of 1 points to 2, next of 2 points to 3 and 3 pointed to null, 3 was the last element.
Now the pointer called 'remaining' is pointing to three, in the last diagram, remaining is the new head, and 'remaining' is returned as a result.
@nitin2n33 explained in great detail how this recursion is taking place > recursion stacks
ikechukwuhenry + 0 comments great
kregex + 0 comments Thanks Hemang for the good explanation
DeCoderReLoaded + 1 comment you can remove
> null
from the following stage
1 > 2 < 3 > null ^ ^   head remaining
and add it as
null ^  1 > 2 < 3 ^ ^   head remaining
and so on...
TajPoovaiah + 0 comments I feel like this is a clearer explaination. Thank you, @DeCoderReLoaded
cornelciky + 0 comments thank you kind sir you're a superhero
harshbisht95 + 0 comments Nicely explained.Thanks bro.
tanmay777 + 0 comments Respectt! _
souravsingla + 0 comments thanks buddy ....it helped a lot
tejasa + 0 comments Bro this was some journey. Thanks!
Mayur16 + 0 comments nice one
conghtse05773 + 0 comments Very detailed explanation. thanksss
ThanoozN + 0 comments [deleted]Avba8 + 0 comments Superb explanation! I'm revising my concepts to prepare for interviews and this really helped before I could give up. Thank you so much!
drkrishnan + 0 comments Very nice explanation, thanks, long way to go! :)
pirimiri + 0 comments it will be overwritten at the next level up, so you set it to null then you go up and set it to the previous node...which is why I think recursion for this problem is not really efficient since you only need to set the next pointer of the original head node to null.
mr_pental22 + 2 comments what is the need for
head.next = null;
angela_pan1992 + 0 comments if we don't break the original link, then there will be a loop. here is a video
ganeshlandge936 + 0 comments It is for single node condition. If we didn't take care of that, head>next>next will result into segmentation fault.
aashil + 2 comments Why can't we do remaining.next = head instead of head.next.next = head. Shouldn't it do the same thing ?
arsenicseven + 0 comments Incase of 3 > 2 > 1 >null where head is 3, head.next.next=head will point the node 2 to node 3 instead of 1 i.e., 3<=>2 X 1>null(X representing no relation and <=> representing a relation where 3.next will give 2 and vice versa)
ArshadAQ + 0 comments That's because, we want to keep remaining unchanged!
If you do remaining.next = head and return remaining, then remaining will keep changing its pointing to the next element, until the recursion fully pops and in the end remaining.next will point to the 1st element, rendering only 2 elements in the list.
Eg:
1>2>3>4
When head = 3 and remaining = 4, remaining.next = head will change to
1>2>3<4
Now still remaining =4, but in the subsequent recursion pop, head will change to 2
Now when that happens and you do remaining.next = head, then remaining.next will now point to 2. ie 4 will point to 2. This will happen until 4 will point to 1 and the list will only have 2 elements.
However, if you wish this doesn't happen, then before returning remaining you could do something like remaining.next = remaining. But then the last pop of recursion would now return the 1st element as head and the list wouldn't be reversed.
Therefore, remaining shouldn't be changed!
pinkRanger + 0 comments Thanks StefanK. It has really helped.
nishamizh + 1 comment head.next.next=head; what is the need for this ? I dont understand this
gschoen + 0 comments Linked list before recursive call:
1>2>3>4>5>*
Linked list after recursive call:
1 5>4>3>2>*  ^   
Since head is still pointing to the node it was before the recursive call (which is now at the end of the list), head.next.next= head; head.next=null correctly places head at the end of the list.
amitj1 + 0 comments Your explanation sucks. You just confused people more. Thanks idiot
hackerrank387 + 0 comments This isn't a tailrecursive solution, and it will blow up the stack when the list is even moderately sized.
EmberQuill + 1 comment Thanks for this. I used the same process you did, but I completely forgot to set the tail node to None so my function kept timing out due to the circular reference.
Here's my Python implementation:
def Reverse(head): if not head or not head.next: return head newHead = Reverse(head.next) head.next.next = head head.next = None return newHead
kunal_tyagi + 0 comments This is really good would you mind walking me through your logic if it's not too much to ask? why head.next.next?
abhinaw + 0 comments Loved it man!
cornelciky + 0 comments thank you kind sir you're a superhero
iamangarg99 + 0 comments [deleted]divya_gracie + 2 comments Simple iteration using stacks:
Node Reverse(Node head) { Stack<Node> stack = new Stack<Node>(); while(head.next != null){ stack.push(head); head=head.next; } Node res = head; while(!stack.empty()){ head.next=stack.pop(); head=head.next; } head.next = null; return res; }
pavitra_ag + 1 comment i used the same approach in c++ but it says that "stack was not declared in this scope". plz help:)
hjames + 0 comments #include <stack>
h170020035 + 0 comments hiiiiii
pandaman + 0 comments I tried to come up with that by myself but I couldn't figure it out. Maybe I'm just bad at recursion, but I wouldn't classify that as "easy."
mo_fa + 0 comments Awesommmmmme solution...For those who are not understanding it try to solve using pen and paper, will be become clear. Really the effort of solving on paper is worth it.
gschoen + 4 comments Recursion usually provides an elegant solution to these types of problems but in this case, it did not appear to have anything over simple iteration:
Node* Reverse(Node *head) { Node *tail, *t; tail = NULL; while (head != NULL) { t = head>next; head>next = tail; tail = head; head = t; } return tail; // Complete this method }
suraj9321 + 0 comments awesome!!
hackerrank387 + 0 comments This should be the topvoted answer
zzmmss + 0 comments really nice and understandable with an artical in csdn, http://blog.csdn.net/skychaofan/article/details/46815007
DEVA_ASURA + 0 comments OMG bruh! How come u got that idea.I'm just speechless.How did u think that smart.You r cool dude.Am following u!
omike1900 + 3 comments Node Reverse(Node head) { if (head == null) { return null; } if (head.next == null) { return head; } Node preNode = null; Node currNode = head; Node nextNode = null; while (currNode != null) { nextNode = currNode.next; currNode.next = preNode; preNode = currNode; currNode = nextNode; } head = preNode; return head; }
shauryaravish + 0 comments Thanks..needed a simple code to understand..
trieuvnhcs + 0 comments we got the node.tail but we destroy the list.
Rehmanali + 0 comments This is not making sense to me. First you point the nextNode to currNode.next that is fine. Then you point the currentnode.... Oh wait, yes it correct. I just did some numerations. Its perfect. But how does that above guy solve with the Reverse() function. What is that function?
pdog1111 + 8 comments Node Reverse(Node head) { if (head == null  head.next == null) { return head; } Node newHead = Reverse(head.next); // reverse all but first head.next.next = head; // make original second point at first head.next = null; // make original first point at nothing return newHead; }
Gautam1002 + 0 comments Is your code working? My logic stands exactly as yours but it isn't working.
btamada + 1 comment Can you explain your code? I don't get what it is doing.
etayluz + 2 comments Recursive implementation in C:
Node* Reverse(Node *head) { // The tail of the list has been reached which // will now be the new head of the reversed list if (head == NULL  head>next == NULL) { return head; } Node* nextNode = head>next; head>next = NULL; Node* newHead = Reverse(nextNode); // reverse the nodes nextNode>next = head; return newHead; }
skarya + 0 comments can you please explain it..........
bala92 + 0 comments cool algo dude
Bonniesaur + 0 comments [deleted]positivedeist_07 + 0 comments Hey, these comments are great :) easily understandable!!
vineettyagi28 + 0 comments It could result in stackoverflowexception if the list is long
anil_pai + 2 comments def Reverse(head): prev, curr = None, head while curr: prev, curr.next, curr = curr, prev, curr.next return prev
CHarmon + 1 comment I like you solution! Although your solution is likely a bit faster, I rewrote it so it is a bit more readable for some of us.
def Reverse(head): prev_node = None next_node = head while next_node: copy_prev_node = prev_node copy_next_next_node = next_node.next prev_node = next_node next_node.next = copy_prev_node next_node = copy_next_next_node head = prev_node return head
thedurphy + 0 comments Really great of you to write it out like this so the logic is easily understandable. For those who need an explanation, the difference between @anil_pai version and @CHarmon is basically the former is performing a simultaneous update on the 4th line. This allows multiple variables to be updated before commiting to memory. @CHarmon does this sequentially, however, this requires original copies to be made so they can be referenced again when updating the following variables.
I really like that both versions were included. This is why I love this site and community.
ikechukwuhenry + 0 comments this is too elegant
Hyeongjun + 3 comments Python
def Reverse(head): prev = None while head: prev = Node(head.data, prev) head = head.next return prev
theparadoxer02 + 1 comment can you explain the code ?
sid31010 + 0 comments stack formation !!! isnt it ?
nei_oliveira + 0 comments Boy, oh boy. You crushed it.
To those who didn't get it, he's exploiting the constructor parameters to create another list entirely. And this one will be reversed because he's setting the 'next' pointer (reference) of each node as the previous node. Legit coding master approach up there.
I did my iterative amateurish thingy, then came here and foung his solution. Mine doesn't ever look pythonic.
def Reverse(head): if head is None: return None prev = None curr = head aux = head.next while curr is not None: curr.next = prev prev = curr curr = aux if curr is not None: aux = aux.next return prev
ig_gladun + 0 comments Amazing!
trollblut + 1 comment My Code:
public static Node Reverse(Node head) { var previous = (Node)null; while (head != null) { var t = head.Next; head.Next = previous; previous = head; head = t; } return previous; }
**My Output:
Your code did not pass this test case.
Input (stdin)
2
4
1 2 3 4
5
2 3 4 5 6
Your Output (stdout)
4 3 2 1
4 3 2 1
Right Answer!
6 5 4 3 2
6 5 4 3 2
Right Answer!
Expected Output
Right Answer!
Right Answer!
Compiler Message
Wrong Answer**
I suspect there is a leftover output in the solution checker.
seanzgraham + 0 comments I am getting the same for C# solution and think you are right.
njuzwr + 1 comment Three solutions listed here:
// Nonrecursive version Node* Reverse(Node *head) { if (head != nullptr) { Node *n = head; head = nullptr; while(n) { Node *m = n; n = n>next; m>next = head; head = m; } } return head; }
// Recursive version Node* Reverse(Node *head) { if (head == nullptr  head>next == nullptr) return head; Node *newhead = Reverse(head>next); head>next>next = head; head>next = nullptr; return newhead; }
// Nonrecursive version, using stack #include <stack> Node *Reverse(Node *head) { if (head != nullptr) { Node *curr = head; std::stack<Node *> ps; while(curr) { ps.push(curr); curr = curr>next; } Node *newhead = ps.top(); while(!ps.empty()) { Node *prev = ps.top(); ps.pop(); prev>next = ps.empty()? nullptr : ps.top(); } return newhead; } return head; }
vineelavelaga9 + 0 comments can u plz explain the non recursive solution without using stack
ozanapaydin + 0 comments Node* Reverse(Node *head) { if (!head>next) return head; /* newHead defined because it is gonna be the NEW head pointer to be linked to tail of current list.*/ Node *newHead = Reverse(head>next); /* returning value from end step of function is going to be tail. So that head will be link to previous node before tail*/ head>next>next = head; /* It was made because of doing tail node's(head shows it at final) next pointer to be NULL. */ head>next = NULL; /* Every final step, the newHead node(everytime it will be newHead(tail of current list)) returned.*/ return newHead; }
Here is my cpp solution. If anyone has a question, i can answer that. As you have seen, i commented my code.
Sort 326 Discussions, By:
Please Login in order to post a comment