Reverse a doubly linked list
byharsha_szqcathy0_0 Share my non-recursive Java solution
Node Reverse(Node head) { Node temp = head; Node newHead = head; while (temp != null) { Node prev = temp.prev; temp.prev = temp.next; temp.next = prev; newHead = temp; temp = temp.prev; } return newHead; }
svadali2 Hey could you explain why this works? because I put a print statement right at the end of the loop after "temp = temp.prev" and it gave me a nullpointer exception. However, when i put that print statement at the start of loop, there was no error; could you give some sort of explanation of this algorithm? thanks.
gswheeler It works like this: in a double-linked list that has been reversed, the values of each node's 'next' and 'prev' fields are swapped (the nodes before and after each node swap positions). The code above does just that; starting at the head of the list it works through the list swapping 'next' and 'prev' values.
As for why you got a NullPointer exception, a pointer without a target has a value of NULL, thus a loop that moves from node to node ends when its "iterator" variable is assigned null (that's why newHead's value is updated before temp's value). In short, your print statement tried to get a field value from said null.
liewsanmin Would appreciate if you explain why you have newHead, can't you just return head?
gswheeler No, because "head" is now at the end of the list, not the beginning.
Also, "temp", being the iterator variable, has a value of "null" when the loop ends (hence newHead being assigned temp's value before temp is updated).
EpsilonAlpha This was so annoying to implement, I always kept getting an extra zero value. Thanks for the elegant solution!
kunalkk477 //see if this can help Node* Reverse(Node* head) { struct Node *current,*prev,*next; if(head==NULL)return NULL; current=head; prev=NULL; while(current!=NULL) { next=current->next; current->next=prev; current->prev=next; prev=current; current=next; } head=prev; return head; }
15scs619 Could u explain current->prev=next; this line meaning??
wryan42675 Minor variation. Four assignments in loop instead of 5. Same algorithm, just eliminate a couple of variables.
Node Reverse(Node head) { if(head==null )return null; head.prev = head.next; head.next = null; while(head.prev!=null){ head = head.prev; Node temp = head.next; head.next = head.prev; head.prev = temp; } return head; }
bhoeting Thought I'd share my recursive solution:
Node* Reverse(Node* node) { // If empty list, return if (!node) return NULL; // Otherwise, swap the next and prev Node *temp = node->next; node->next = node->prev; node->prev = temp; // If the prev is now NULL, the list // has been fully reversed if (!node->prev) return node; // Otherwise, keep going return Reverse(node->prev); }
etayluz C solution with recursion:
Node* Reverse(Node *head) { if (head == NULL || head->next == NULL) { return head; } Node* nextNode = head->next; head->next = head->prev; Node* newHead = Reverse(nextNode); nextNode->next = head; return newHead; }
Belphegor I'm not seeing how this can be correct, you aren't even fixing the previous links, so your code will pass only because the test case is not wide enough.
Kingu how does every node's prev gets changed here ?
my C++ recursive solution
Node* Reverse(Node* head) { // Complete this function // Do not write the main method. if(head==NULL){ return head; } else if(head->next==NULL){ head->next=head->prev; head->prev=NULL; return head; } Node *prevPtr=head->prev; Node *nextPtr=head->next; head->next=prevPtr; head->prev=nextPtr; return Reverse(nextPtr); }
sahil651996 Genius!
haotie python3 version:
def Reverse(head): if not head: return head head.next, head.prev = head.prev, head.next if not head.prev: return head return Reverse(head.prev)
nagacharan will you explain this code?
JB555 I like this solution, simple and elegant.
In python you can switch variables in a single line like shown above, so the code goes through each node at a time reversing the connections until you hit the final node.
The last node returned would be the final one encountered, which is now the first element.
mohitaggarwal516 thanks man !! i was trying the similar solution bhoeting's but ' if (!node->prev) return node; ' was not striking to me...
can anyone tell me after completion of program if we run it for the display, how is end of the linked list is handled???
destroyer08 This part was much like learn with fun ... requesting same for stack, queue, tree and other data structure. It will help me a lot.
PRASHANTB1984 glad to know this was of use!
dhananjay77 It was really nice idea to just implement the function and test. It's really helpful. We just had to focus on the main logic. It's similar to what people expect in interview.
Thanks!
zsljulius Man, this question seems so easy but mind twisting. Good job in coming up with this question.
ghsatpute Just that, most of the time I wasted on looking out understanding the environment rather than solving problem :(.
Thrashans "This part was much like learn with fun" These are my exact thoughts!
ankurk007 Python3:
def Reverse(head): curr = None while head: nxt = head.next curr = head head.next = head.prev head.prev = nxt head = nxt return curr
onuremreerol Here is a easy solution. If you have any question just ask. :)
Node* Reverse(Node* head) { Node *temp; Node *itr = head; while (itr) { temp = itr->next; //reserve the next itr->next = itr->prev; //swap prev and next itr->prev = temp; head = itr; //we do not know if there is a next element itr = temp; //iterate to next } return head; }
Narshot nice sol bro
Tara_123 nice solution
Hemanth_Rao can you explain what head= itr does?
15scs619 itr->prev = temp !! Bro explain this line !!
pdog1111 It seems like the tests aren't thorough enough. if you reverse the list as if it were a singly linked list (eg ignoring all prev pointers) you get full credit.
Node Reverse(Node head) { if (head == null || head.next == null){ return head; } Node newHead = Reverse(head.next); // head.next.prev = head.next.next; head.next.next = head; // head.prev = head.next; head.next = null; return newHead; }sroy1532 I guess you were getting a error because you were not setting the prev pointer to null if the head.next == null..
For example, try this (passes all test cases):
Node Reverse(Node head) { if (head == null) { return head; } if (head.next == null) { head.prev = null; return head; } Node newHead = Reverse(head.next); head.next.next = head; head.prev = head.next; head.next = null; return newHead; }
samahuj1994 Simple Java iterative java solution
Node Reverse(Node head) { if(head == null) return null; if(head.next == null) return head; Node temp = null; Node current = head; while(current != null){ temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } if(temp!=null) head = temp.prev; return head; }
Mothi [deleted]
igauravsehrawat Question says "you are given head" while the pointer returns you the tail !! So if someone is getting wrong answer. you can correct yourself. #Cheers# Happy Coding
abhiranjan Hi Gaurav, it is already mentioned in the
output formatthat the head of reversed list should be reversed. Please correct me if I get your query wrong.abhiranjan \* head of reversed list should be _returned_.
Surbhi94 Helped me :)
Snelius Node *node = head; Node *prev = head; while (node != NULL) { prev = node; node = node->next; prev->next = prev->prev; prev->prev = node; } return prev;
pulekar_aditya Another way (Using Recursion):
Node Reverse(Node head) { if(head == null || head.next == null){ return head; } Node top = Reverse(head.next); head.next.next = head; //Remove the below line if you are looking to reverse a singly linked list. Simple :) head.prev = head.next; head.next = null; return top; }
Sort 182 Discussions, By:
Please Login in order to post a comment