Reverse a linked list
Reverse a linked list
StefanK + 23 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 + 3 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 + 20 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 + 1 comment 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.
josef_klotzner + 0 comments beginners might be curious what LIFO means  it is: Last in, first out
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
[deleted] + 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! :)
smithosagie24 + 0 comments Thanks for taking time to explain.
peebee01 + 0 comments Great explanation, I understood it perfectly!
cold3018 + 0 comments This is the explanation I was looking for all these days , finally I got it
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.
vuquocson1995 + 0 comments Could you please explain that why Node "Remaining" wasn't change when heah reference to 1? Thank you so much.
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 + 1 comment 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!
trungpham2012 + 0 comments Thank you so much for this explanation! I was doing that and not sure why it didn't work
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 + 2 comments Your explanation sucks. You just confused people more. Thanks idiot
josef_klotzner + 0 comments Since you are not able to do it better, you might be below his level, so be careful calling somebody something that could reflect to yourself!  downvote for your comment
kalerutuja862 + 0 comments Why would you call anyone an idiot ? Who gave you this right? He tried to help people by writing dowm some explanation in his manner. If you didnt understand it or didnt find it usefull ,is it his fault?
hackerrank387 + 1 comment This isn't a tailrecursive solution, and it will blow up the stack when the list is even moderately sized.
mark_sch + 0 comments C, C++, Java and C# don't guarantee tail call optimization so it will likely blow up the stack either way.
EmberQuill + 2 comments 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 + 1 comment This is really good would you mind walking me through your logic if it's not too much to ask? why head.next.next?
josef_klotzner + 0 comments it is explained in very deep detail related to C++ solution above. As logic is the same it should be possible for you to understand above statements, but may be not explicitly related to your question only. So, head is reference to "head" before the next call of a recursion. head.next is referencing to same "head" as within next recursion call. And it's next is (head.next).next, which is the pointer to next element. This pointer is set to "head", which is basically previous element. This is exactly what we want. Instead of pointing to next element we point to previous element, causing reversing the list.
isahurrutia + 0 comments Another recursive Python solution:
def reverse_helper(node): if node.next is not None: reverse_helper(node.next) node.next.next = node node.next = None def reverse(head): last_node = head while last_node.next is not None: last_node = last_node.next reverse_helper(head) return last_node
abhinaw + 0 comments Loved it man!
cornelciky + 0 comments thank you kind sir you're a superhero
iamangarg99 + 0 comments [deleted]divya_gracie + 5 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
anshul_abhinav + 0 comments This is a much cleaner way to solve this problem. It does use an explicit extra Stack, but so does recursion, inherently.
nihaal12_singh + 0 comments Bad approach, why increase so much space complexity when the job can be done via updating the pointers.
GilbertS + 0 comments Why are you using another data structure (Stack) to implement operations on another data structure (LinkedList) ?
pandaman + 1 comment 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."
josef_klotzner + 0 comments and only 5 ( in words "tiniwiny five" ) points is a shame :)
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.
vuanhnguyenduc + 0 comments you sir, just made my day! Thank you for the awesome solution :)
bilotiavaibhav + 0 comments I couldn't get how can we return more than once from a function.Like at the very beginning we are returning head and then "remaining" node!Only one value can be returned from a method.Isn't it?
braj_jaipur + 1 comment Below line is not clear to me in first look. I'll come back later on.
head.next.next = head;
josef_klotzner + 0 comments it is explained in very deep detail related to C++ solution above. As logic is the same it should be possible for you to understand above statements, but may be not explicitly related to your question only. So, head is reference to "head" before the next call of a recursion. head.next is referencing to same "head" as within next recursion call. And it's next is (head.next).next, which is the pointer to next element. This pointer is set to "head", which is basically previous element. This is exactly what we want. Instead of pointing to next element we point to previous element, causing reversing the list.
sauravdas90 + 1 comment Have you tried an iterative solution to it?
josef_klotzner + 1 comment The chance to get it with a bug is much higher when trying iterative compared to simpler code of recursive solution, which makes it also simple to get correct solution. But if you like to do it iterativly, i don't mind :)
sauravdas90 + 0 comments sometimes in an interview you may be asked both the approaches, so I thought of asking it. Thanks for the insight.
janis_stolzenwa1 + 1 comment A slightly simplyfied version of the fucntion body:
auto node = head; if(head>next){ node = reverse(head>next); head>next>next = head; head>next = NULL; } return node;
chhayaprakashj + 0 comments how about this: here is another soultion but it is only prinitng 1 but debug output prints everything right...how? SinglyLinkedListNode* reverse(SinglyLinkedListNode* head) {
if(head==NULL  head>next==NULL){ cout<<head>data<<"\t"; return head; } SinglyLinkedListNode* temp=reverse(head>next); temp>next=head; head>next=NULL; cout<<head>data<<"\t"; return head;
}
abhimanyuaj001 + 0 comments python3
class Node: def __init__(self,data): self.data=data self.next=None class SinglyLinkedList: def __init__(self): self.head=None def insert_node(self,data): node=Node(data) node.next=self.head self.head=node def reverse(head): return head
engineervinay + 0 comments [deleted]aneeshreddy_2910 + 0 comments here everytime head>next is pointed to null to attain the final tail node condition
gschoen + 9 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 + 1 comment 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!
firozbhaikardar1 + 0 comments madrchod utube se nikala hein isne yeah.. aur tu chutiya ban gya
nitesh150699 + 0 comments awesome work :)
amanraihot + 0 comments Awesome bro yo simplified the solution and thanks I had also thought in same way but was doing some mistake,
josef_klotzner + 1 comment understanding your code needs deeper C(++) knowledge, things with pointers (*) and > ... 1) the charming thing on recursive solution is because of it's simple syntax 2) recursion is a little shorter 3) with your solution you are shifting the tail towards the head AND change pointers, in recursion the result node stays from beginning to end, just changing pointers
.... only to mention some ... :)
(some sarcasm: .... being able to be "copied" into nearly every other language and then all the people here are telling proud: "i solved this challenge") ... can't stop rolling on the floor because of laughing :)
lumrosset + 0 comments The iterative solution is more efficient space and timewise. Recursion is very nice for us to read and understand, but has some overhead and takes stack space for every function call. Sure, for an exercise such as this or a small number of calls it is fine, but for some more heavyweight application it will cost more.
josef_klotzner + 0 comments i found an even shorter amazingly easy iterative solution in python on this site:
def Reverse (self): prev = None while self: prev = SinglyLinkedListNode (self.data, prev) self = self.next return prev
gschoen + 0 comments The recursive solutions presented here are not tail recursive. If you wish to use recursion then an auxiliary tail recursive function should be used:
Node* ReverseTR(Node *X, Node *Y) { Node *t; if (X == NULL) { return Y; } else { t = X>next; X>next = Y; return ReverseTR(t, X); } } Node* Reverse(Node *head) { return ReverseTR(head, NULL); }
omike1900 + 4 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?
mehedi_hossain16 + 4 comments The first two if statements are covered by the while loop. slightly better version (in C++):
SinglyLinkedListNode* reverse(SinglyLinkedListNode* head) { SinglyLinkedListNode* prevNode = nullptr; SinglyLinkedListNode* currNode = head; SinglyLinkedListNode* nextNode = nullptr; while(currNode != nullptr){ nextNode = currNode>next; currNode>next = prevNode; prevNode = currNode; currNode = nextNode; } head = prevNode; return head; }
sarveshbhosale31 + 0 comments Awesome logic bro
alcidvincent + 0 comments Thanks bro I became a hackerman
arlandbindoy + 0 comments really appriciate the code it helps me pass my prelim
doguilesmenard + 0 comments Thanks ma men!
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 + 3 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; }
c650Alpha + 0 comments Thanks. Recursion is awfully useful in Linked Lists, but sometimes difficult to wrap one's head around.
btamada + 0 comments ^ I agree! Recursive algorithms confuse me the easiest!
vonstuckrad + 0 comments Dont all of this recursive calls blow up the stack? Seems like inplace iteration is the way to go here. Also, might as well use a regular stack for storing the pointers, seems less confusing to me.
EDIT: I tried it out, and even a list with only 5000 elements already throws a stack overflow. So this solution might work, but is really not usefull at all. (Tested it on windows, I believe the stack size is around 1MB)
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 + 1 comment It could result in stackoverflowexception if the list is long
josef_klotzner + 0 comments absolutely no problem with just a thousand elements ^^
Hyeongjun + 6 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!
minhdann_g + 0 comments holy jesus christ ! what an exploit master
SanaKhanam + 0 comments Why am i getting the error Node is not defined?? Can someone explain!
Ambious + 0 comments Amazing solution.
Mine was also hacky, but a little less clever:order = [] runner = head while runner: order.append(runner) runner = runner.next order.reverse() for i in range(len(order)): if i < (len(order)  1): order[i].next = order[i+1] else: order[i].next = None return order[0]
Sort 481 Discussions, By:
Please Login in order to post a comment