We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Data Structures
  3. Linked Lists
  4. Reverse a doubly linked list
  5. Discussions

Reverse a doubly linked list

  • bhoeting + 4 comments

    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 + 3 comments

      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 + 0 comments

        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 + 1 comment

        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 + 0 comments

        Genius!

    • haotie + 1 comment

      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 + 1 comment

        will you explain this code?

        • JB555 + 1 comment

          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.

          • jsqihui + 1 comment

            I like this, the if not head is only for checking if the list is empty. and if not head.prev is the terminate condition for recursive, am I right?

            • JB555 + 0 comments

              Hi, yes, you are correct on both counts.

    • mohitaggarwal516 + 0 comments

      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???

    • Muntaha_Islam + 0 comments

      Will it really work with prev in here:

      if (!node->prev) return node;

      Shouldn't it be node->next?