sophist_pt You could do it recursively which is a lot neater. The code below is in Java.
void ReversePrint(Node head) {
if(head == null) ; else{ ReversePrint(head.next); System.out.println(head.data); }}
andre_nunes Recursion never felt so good :D
mihai_condur11 That conditional is a bit ugly, why not
if(head == null) return; ReversePrint(head.next); System.out.println(head.data); // OR if (head != null) { ReversePrint(head.next); System.out.println(head.data); }
sujitoic nice
Infinity_Coder So true :)
chaudhary__jr So true. :D
thrinath999 void ReversePrint(Node *head) { // This is a "method-only" submission. // You only need to complete this method. if(head){ ReversePrint(head->next); printf("%d\n",head->data); } }
bharathi14 I did not understand the logic. Can you please explain? Thanks!
StefanK I took sophist_pt's code and altered it a bit to hopefully make it more intuitive.
void ReversePrint(Node head) { //if the head is not yet null... if (head != null) { //call the function again but on the next node ReversePrint(head.next); /*---------------------------------------------- The recursion will get "stacked" right here! The code below this area will not get called until we go back up through the recursive stack. -----------------------------------------------*/ System.out.println(head.data); } }Here's a code trace for an example. We have a linked list of three elements [1] -> [2] -> [3] Let's begin by calling the head.
A. RevPr(1) if elemenent 1 is not yet null, move on. It's not null! Call again on next, element 2... B. RevPr(2) if elemenent 2 is not yet null, move on. It's not null! Call again on next, element 3... C. RevPr(3) if elemenent 3 is not yet null, move on. It's not null! Call again on next, element 4... D. RevPr(4) if elemenent 4 is not yet null, move on. Wait, it is null! No more calls, we're done.So we just built this recursive stack. [RevPr1(RevPr2(RevPr3(RevPr4)))] Now we have to execute the function that is innermost. Why? Because that's where we were most recently!
D. RevPr4. That most recent call failed the condition. Nothing is printed. -->[RevPr1(RevPr2(RevPr3()))] C. RevPr3. RevPr3 never finished the code in the if statement, so now we print 3! -->3 -->[RevPr1(RevPr2())] B. RevPr2. Now we need to print 2! -->3 -->2 -->[RevPr1()] A. RevPr1. The last call! Print 1! This call is done, and now everything is done. -->3 -->2 -->1This function was written from sophist_pt's brilliant code.
bharathi14 Got it. Thanks!
sandymark0346 Youre amazing thank you
StefanK My pleasure! Recursion hurts my brain too... But eventually with enough practice one is able to understand when and how recursion is useful. (Hopefully without spending a half-hour to trace the process out like I did.)
thrinath999 void ReversePrint(Node *head) { // This is a "method-only" submission. // You only need to complete this method. if(head){ ReversePrint(head->next); printf("%d\n",head->data); } }
Mathew_Sam Really helpfull!!
DrManhattan Many thanks.. this helped tremendously
:D
AleksaVidovic Very educational. Thank you!
vipinjain007 Hi ,Could you give more details about 2nd paragraph .How it's >[RevPr1(RevPr2(RevPr3()))]?
trungbnguyen308 I've been seeing recursion a lot and only vaguely understand it, but with your explanation, it's all clear now. Thank you!
raulrios1 Thank you!!!
thrinath999 [deleted]
andy_linmu Great explanation
thrinath999 [deleted]
Abushawish Seriously amazing, should be a teacher or a prof.
thrinath999 [deleted]
m4rtin_t This comment will probably get burried, but basically...if i understood this correctly, the last one who calls and enters the if (head != null) get's to do the print statement first.
Then it unravells until the first one who called the if statements get's their turn to print it out.
shantanuraje that made it a little more clearer . thanks :)
thrinath999 [deleted]
15bit054 Your explanation was very helpful..
Javabux_ That was a beauty. I believe you cleared the concepts of all recursive functions for me.
thrinath999 [deleted]
Bharani19797 massssss...
aravindhsai29 UR FUCKIN AWEOSME MAN
BuilderDeviser beautiful explanation. One of the clearest I've seen on recursion honestly lol
ipg_2016069 awesome explained recursion . it help for beginner ! keep it.
talentandstyle thank you so much!
truongminhphung1 Thank you so much
uthejks thanks a lot bro..
HuangZhenyang fantastic!
thrinath999 void ReversePrint(Node *head) { // This is a "method-only" submission. // You only need to complete this method. if(head){ ReversePrint(head->next); printf("%d\n",head->data); } }
madaraicu I don't know why this solution causes runtime exception...? Did this happen to someone else ?
StefanK Have you figured it out? Can you post your code? Both versions of the solution above work.
alfred_b_wong Hi,
I got this runtime exception as well. For me, it was for the Test Case #1 where they have an input of just 0 for one of there queries. Normally, it is a number for the # of nodes in the linked list followed by a set of numbers that need to be reversely printed.
You can test it out by using custom input of the Test Case #1 input and removing the 0 from the input data and changing the first 5 to 4 queries after.
sami_sherif can u please explain your code, the recursion part in particular
boranyildirim I think it is better just write if(head != null) instead of if-else.
isa01 I wonder can it break the stack with sufficient linked-list length?
vtsvang It can and will
desaim Yeah. Recursive solutions generally don't work well when n is very big because of the demands on the stack. Classic example is computing the Fibonacci numbers. Compare the recurisve solution against the iterative one.
VictoriaB Yes, I agree and this can be an important consideration for large data sets or relatively large data sets on platforms with restricted stack sizes. If Hackerrank doesn't already, I think they could include variations on problems like this that enforce iterative solutions.
chett2001 This immediately came to mind for me. It might look really nice, and really neat, but you would never do this in reality. You run the risk of overflowing the stack.
gihanchanaka Beautiful!
d_negative_zero if(head == null) { return; } ReversePrint(head.next); System.out.println(head.data); This code is more optimized and effiecient.vipinjain007 Hi , How this code will display reverse data?
LearnCodeFun This may be helpful in understanding recursion better if you didn't get StefanK's explanation. https://www.youtube.com/watch?v=neuDuf_i8Sg
Infinity_Coder Thanks a lot!!!
luca_guarro You vs. the guy she tells you not to worry about
Inuyasha_ void ReversePrint(Node *head){ if(head==NULL) return; else{ ReversePrint(head->next); cout<<head->data<<endl; } }
C++ solution
keerthana123456 how it works??
-
-
harikaprathi It's through recursion, ex : 1->4->8->9 In this first the head will move till head is NULL and then returns control to the previous call then printing of the last ele is done then the control is returned to the previous call then printing of the last second ele and so on.
ksatish8886 really...its a wonderful thought
TinaNguyen290 Who do I know that it's traversing in the reverse direction? It's not a double linked list so it's hard to go back when you can only move forward...
MAYUR_2 i have done without recurrsion:
void ReversePrint(Node head) {
Node node=head; Node node1=head; int c=0; while(node!=null) { c++; node=node.next; } //System.out.println(c); int arr[]=new int[c]; int i=0; while(node1!=null) { arr[i]=node1.data; i++; node1=node1.next; } int j; if(c>0) { for(j=(c-1);j>=0;j--) { System.out.println(arr[j]); } }}
bhavik4748 same here in C#:
**
public static void ReversePrint(Node head) { if (head != null) { var tempNode = head; var counter = 1; while (tempNode.Next != null) { ++counter; tempNode = tempNode.Next; } int[] arr = new int[counter]; counter = 1; tempNode = head; while (tempNode.Next != null) { arr[counter - 1] = tempNode.Data; ++counter; tempNode = tempNode.Next; } arr[counter-1] = tempNode.Data; for (int i = arr.Length - 1; i >= 0; --i) { Console.WriteLine(arr[i]); } } }
**
carlosrobertode1 if (head != null) { ReversePrint(head.Next); Console.WriteLine(head.Data); }
narayana_8 this code is similar to yours but it gives a null pointer exception.can you explain why?
if(head==null){ return; } else{ head=head.next; ReversePrint(head); System.out.println(head.data); }
ksohith Because you are first putting it as head.next which means if it IS null, it will already be at head.next and the return will basically return to the pre-recursion of the last function just to get print a null value
What his code does is, if head.next is null, it will return so that head.data will be printed, otherwise, head=head.next will happen and that will be put into the same function
narayana_8 [deleted]riwiem Even denser in Python:
def ReversePrint(head): if head: ReversePrint(head.next) print(head.data)
garrettjgregory [deleted]ishanshekhar0502 here's my take to it
void ReversePrint(Node *head) {if(!head) return; ReversePrint(head->next); printf("%d\n",head->data); }
vlad_polyakov C#
public static void ReversePrint(Node head) { if (head != null){ ReversePrint(head.Next); Console.WriteLine(head.Data); } }
undefitied I'm not from Java, but if there is no special kind of execution queue, code above should print in the direct order, not in reversed. So why?
syousef Here's what I don't like about these simple problems. The requirements aren't clear. How large is the linked list? Do you want to use recursion on a huge list and blow the stack? Do you have enough memory to create a copy? Do you want to optimize for space complexity or time complexity? Should the solution be non-destructive to the passed in list? (It doesn't help that you're not shown the implementation of the rest of the code). This is a nifty site and a great tool for exercising your programming skills but it absolutely horrifies me that it has become a darling site for IT recruitment. A good programmer isn't a dirty programmer who doesn't think about real world complexities and instead aims for the quickest solution or least number of lines. The emphasis on speed also promotes bad habits in terms of commenting and formatting code.
nayab9 Agreed 100%. The problem though, ultimately, are the companies who ask these questions during interviews. When the #1 most desired software company does it, you can bet on it trickling down to the rest.
gauravgrover95 here are some pro people.... :) Thanks for the enlightment. :) It helped to expand my vision. :)
kaboc Yep, as long as its not for recruitment you should come with your own ideas. You like recursion its fine, there is no problem to explain to interviewer later why u use that solution, but also having in mind other disadvantages.
surajdubey I used Stack to solve this problem.
java.util.Stack<Node> stack = new java.util.Stack<>(); if(head != null) { Node currentNode = head; while(currentNode!=null) { stack.push(currentNode); currentNode = currentNode.next; } while(!stack.isEmpty()) { System.out.println((stack.pop()).data); } }jattilah Yes that was my solution, except in C++. Recursion has its place, but if you aren't darned sure of the depth, it's smart to build in a counter and bail after a certain length to avoid stack overflow,
GrahamS Yeah I wouldn't use recursion here unless I knew there was some limit on the size of the linked list.
Simple iterative C++ solution equivalent to surajdubey's Java:
#include <deque> void ReversePrint(Node *head) { deque<int> values; for (Node* current = head; current != 0; current = current->next) { values.push_front(current->data); } for (auto x : values ) { cout << x << endl; } }
mohitpawar10 Thank you! I did't knew about deque library. Auto increment for loop too.
llahiru [deleted]
brous smart!
nm1511 They really should ban posting solutions in discussions already.
gauravgrover95 I am not a professional but I have heard that Stack is just another form of recursion where you are maintaining your stack yourself. You could be smart and use in-built stack by using recursion.
tplaskota built-in stack is heavily memory limited, while explicitly declared one is not. Also recursion will place additional overhead information on native stack. Explicit stack will only put values there, while native one will put parameters as well as function name on that stack. On top of that recursion is horrendously annoying to debug in bigger environment.
iambanker Neat recursive solution in
Python3def ReversePrint(head): if head: ReversePrint(head.next) print(head.data)
thedurphy Really elegent!
varunglbian why cant we use iterative method here
kistanod We can, he just figured out a very beautifyl way to do it.
gauravgrover95 Am I the only crazy person here who didn't even thought of recursion and created another reversed LinkedList just to output the characters in reverse order? :/
void ReversePrint(Node *head) { struct Node* last = NULL; while(head != NULL) { struct Node* temp = new Node; temp->data = head->data; temp->next = last; last = temp; head = head->next; } while(last != NULL) { cout<<last->data<<endl; last = last->next; } }
VictoriaB You are not alone. A similar option I took is to reverse the list in place and then re-reverse the list while performing the print. This takes two traversals, but doesn't require additional memory:
void ReversePrint(Node *head) { if (!head) return; auto reverse = [](Node* head, bool print) { auto curr = head->next; head->next = nullptr; auto prev = head; while (curr) { if (print) cout << prev->data << "\n"; auto temp = curr->next; curr->next = prev; prev = curr; curr = temp; } if (print) cout << prev->data << "\n"; return prev; }; head = reverse(head, false); head = reverse(head, true); }
hoyun293 that's what i came up with ! you already implemented very well! thanks!
maddineni_rahul1 Java solution using Stack
void ReversePrint(Node head) { Node temp = head; Stack s = new Stack(); while(temp != null){ s.push(temp.data); temp = temp.next; } while(!s.empty()){ System.out.println(s.pop()); } }
jq_cahill Just learning about Stack and this was helpful...simple and clean. Thanks.
AffineStructure Python3 solution. There is no reason for these silly reverse for loops.
def ReversePrint(head): if head is None: return None else: stack = [] while head: stack.append(head.data) head = head.next while stack: print(stack.pop())
biddybap Nice use of pop() here - good example of such a fundamental list method. My solution was the same up to that point, my first version had a "for item in items: print item".
Thanks, you're my lesson of the day! My Python code below with my version blanked via comment, yours is generally tighter than mine but the principle is the same:
def ReversePrint(head): if head is None: return head else: items = [] currentNode = head while currentNode is not None: items.append(currentNode.data) currentNode = currentNode.next while items: print(items.pop()) """else: items.reverse() for item in items: print(item)"""
karthikx2 Did anybody try with javascript? I am getting error in the code given my hackerank. Screenshot attached.
michael_heimbach function reversePrint(head) { if(head.next!==null) { reversePrint(head.next); } console.log(head.data); }
mdshadan Python
def reversePrint(head): currnode=head a=[] while currnode!=None: a.append(currnode.data) currnode=currnode.next for i in a[::-1]: print (i)
Sort 348 Discussions, By:
Please Login in order to post a comment