CODEWITHSUNDEEP
c++data-structureslinked-listdoubly-linked-list
Tejas Sharma
Tejas Sharma

Reputation: 53

Reversing a linked list between two nodes

I'm working on some homework for a CS class, and struggling a bit with a function that's meant to reverse a doubly linked list between two given nodes. I'm pretty confused about what I'm doing wrong, and I've searched google and SO and I can't find anything that helps me out.

I have a doubly linked list, and I'm essentially using this function as a helper function to reverse it between two nodes that are given as the parameters of the function.

Below is the code for the template, commented so you know my thought process

template <class T>
void List<T>::reverse( ListNode * & startPoint, ListNode * & endPoint )
{
    //make sure that none of the pointers are null and that the start and 
    //end points aren't the same
    if(startPoint == NULL || endPoint == NULL || startPoint == endPoint)
        return;
    //Make two nodes denoting everything happening before the
    //start and everything after the end
    ListNode *before = NULL;
    ListNode *after = NULL;
    if(startPoint->prev != NULL)
        before = startPoint->prev;
    if(endPoint->next != NULL)
        after = endPoint->next;
    ListNode *temp = startPoint;
    ListNode *temp2;
    //run a loop actually reversing the list. I have identified
    //that this is where the problem is happening (obviously)
    //for some reason the prev pointer for every node is being set to null
    //so if I had a linked list with 1 2 3 4 5
    //after running this it's just 5
    while(temp!=endPoint && temp!=NULL){
        temp2 = temp->next;
        if(temp->prev!=NULL);
            temp->next = temp->prev;
        if(temp2!=NULL)
            temp->prev = temp2;
        temp = temp2;

    }
    //switch around the end and start pointers
    endPoint = startPoint;
    startPoint = temp;
    //make sure it's integrated into the rest of the linked list
    if(before != NULL){
        before->next = startPoint;
        startPoint->prev = before;
    }
    if(after != NULL){
        after->prev = endPoint;
        endPoint->next = after;
    }
}

So, any ideas? I've understood where the problem is happening, and what it is, but I haven't understood why it's happening, and how to fix it.

Also, feel free to let me know if you think I'm doing something redundant or unnecessary, I have a tendency to do that sometimes.

EDIT: This is an inclusive function, so if you called it on a linked list {1, 2, 3, 4, 5, 6} with pointers pointing to nodes with value 2 and 5, then the linked list would be changed to {1, 5, 4, 3, 2, 6}

Upvotes: 0

Views: 942

Answers (1)

Beta
Beta

Reputation: 99094

The problem is with the ends of the sublist.

You haven't given a complete example (which would have helped), but suppose we start with the list {1, 2, 3, 4, 5}, and we attempt reverse(s, e), where s and e are pointers that point to 2 and 4. (So our desired result is {1, 4, 3, 2, 5}.)

This is where my skill at ASCII art fails, but the 'next' and 'prev' pointers look like this:

1-->2-->3-->4-->5

1<--2<--3<--4<--5

When control leaves the while loop, they look like this:

1<->2<--3   4-->5
1   2-->3<->4<--5

which is almost what we intended, but the process stopped one node to soon (the 4 has not been reversed). After it is "integrated into the rest of the list", they look like this:

  ________ ___
 /   /    \   \
1   2<--3  >4-->5
1   2-->3-->4   5
 \___\_____/___/

Not very clear, but if you start at the beginning of the list and move forward, it goes {1, 4, 5}, and if you move backward from the end it goes {5, 2, 3, 4, 1}. You have broken the doubly-linked condition that if a.next points to b, then b.prev points to a, and vise-versa.

My advice (apart from drawing more arrows with pencil and paper) is to remove the sublist from the list, reverse it, then splice it back in; trying to reverse it in place is confusing.

Upvotes: 1

Related Questions