CODEWITHSUNDEEP
cpointersdoubly-linked-list
zolo
zolo

Reputation: 149

why original doubly linked is modified when i reverse using this method?

I am trying to reverse a doubly linked list using iterative approach and i'm struck on the part where my original list is being modified even though i'm not using a pointer to pointer style modification of original list.

This is the reverse function i am using, head is a local variable declared in main like Node* head = NULL; and is already populated with a set of values. 

Node* reverse_iterative(Node* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    Node *prev, *current=head, *temp;
    while(current != NULL)
    {
        current->prev = current->next;
        current->next = temp;
        temp = current;
        current = current->prev;
    }
    return temp;
}

This is how i used this in main :

Node* rev = NULL;
rev = reverse_iterative(head);

Here is the output i got:

original list: 15 <=>25 <=>35 <=>45 <=>55 <=>65 <=>75 <=>
making the list actually reverse: 75 <=>65 <=>55 <=>45 <=>35 <=>25 <=>15 <=>
after reversing, the original list now: 15 <=>

I couldn't get the part where my original head node was being modified.

Upvotes: 0

Views: 68

Answers (2)

Mikkel K.
Mikkel K.

Reputation: 373

If I understand you correctly, you don't want your original list to be modified at all.

But the loop modifies the original element. For example, current starts out pointing to the head element and you then modify its next and prev. This means the original head element is now modified.

Upvotes: 3

WhozCraig
WhozCraig

Reputation: 66244

Look carefully at your while-loop, and consider the following statement on the initial iteration of the loop:

current->next = temp;

What is in temp at the time of this assignment? Exposing more of the code, we have:

Node *prev, *current=head, *temp;
while(current != NULL)
{
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

Note that temp is uninitialized and thus an undefined pointer value. Your original head-ptr next ptr is being reset to garbage held in the uninitialized temp.

Fix this by doing the following:

Node *current=head, *temp=NULL;
while(current != NULL)
{
    temp = current->prev;
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

I've not had a chance to test it, but that should get you closer to what you're looking for.

Upvotes: 3

Related Questions