CODEWITHSUNDEEP
data-structureslinked-listreversedoubly-linked-list
Andrew Tsay
Andrew Tsay

Reputation: 1953

Reverse a doubly linked list

Here's my simple linked list program that creates a doubly linked list, and it works.

#include <iostream>
using namespace std;

typedef struct node {
  int data;
  node *next;
  node *prev;
}node;

void printList(node *temp);

int main()
{
    node *head;
    head = new node;
    head->prev = NULL;
    node *next = head;
    node *prev = head;
    node *temp = head;
    node *current = head;

    //creates 100 nodes, last one points to next
    for(int x = 0; x<100; x++)
    {
    temp->data = x;
    current = temp;
    temp = new node;
    current->next = temp;
    temp->prev = current;
    temp->next = NULL;
    }
    //=========================================

    printList(head);

    //=========== set everything to head ===========
    current = head;
    prev = head;

    //============= reverses linked list ============
    while(current->next != NULL)
    {   
    next = current->next;   //moves next pointer to next node
    current->prev = next;   //points current's previous to next node
    current = next;         //set current pointer to next node
    current->next = prev;   //set current's next to previous node
    prev = current;         //move prev node up to current
    }
    //================================================

    printList(head);
    cout<<"done";

    return 0;
}    

void printList(node *temp)
{
    while(temp->next != NULL)
    {
        cout<<temp->data<<'\n';
        temp = temp->next;
    }
}

Once I add the reverse function though, it hangs. Actually, the function itself works, but in an IDE, when I LOOP it, it prints out all the values, then just hangs(sits there with blinking cursor) and does nothing.

Solution: Got it to work. This is what my function ended up being.

current = head;         //set current pointer to head
prev = head;            //set previous pointer to head


next = current->next;   //moves next pointer to next node
current->next = NULL;   //set the next of the header to NULL, because it will actually be the last
                        //node of reversed list.
current->prev = next;   //set previous of the header to the next node.

while(next != NULL)
{
current = next;
next = current->next;
current->prev = next;
current->next = prev;
prev = current;
}

Upvotes: 0

Views: 2647

Answers (2)

Vishal
Vishal

Reputation: 18

Look this simple solution..

Node* Reverse(Node* head)
{
Node * curr=head;
Node * prev=NULL,* nxt=NULL;

while(curr!=NULL)
    {
    nxt=curr->next;

    curr->next=prev;
    curr->prev=nxt;

    prev=curr;
    curr=nxt;
    }

return prev;
// Complete this function
// Do not write the main method. 
}

Upvotes: 0

GreenAsJade
GreenAsJade

Reputation: 14685

Your reverse algorithm is basically broken.

On the first pass through:

current = head; //  Current is pointing at node 0, node0->next is 1 from before
prev = head; // Prev is pointing at node 0

next = current->next; //  next is pointing at 1
current->prev = next; //  node0->prev is pointing at 1
current = next;       //  current is pointing at 1
current->next = prev  //  node1->next is pointing at 0

then next pass

next = current->next //  read up there ^^^   node1->next is pointing at 0

... so next goes back to to node 0.

That is not what you meant to do - it causes you to loop around nodes 1 and zero repeatedly, instead of progressing to node 2 and beyond...

Note that you could have easily debugged this if you put this code into the reverse loop:

cout<<"\nStarting iteration"
cout<<"\nNext is at" << next->data
cout<<"\nCurrent is at" << current->data
cout<<"\nCurrent->next is" << current->next->data

etc... doesn't take long to type, reveals all :)

(probably you would cut it down to do 3 instead of 100)

I just did the steps for 3 nodes manually (on paper) to deduce this answer...

Upvotes: 1

Related Questions