CODEWITHSUNDEEP
c++linked-listreverse
Adam
Adam

Reputation: 93

reverse part of a doubly linked list

I'm trying to implement my own list class but am having trouble reversing just part of my list.

Revelant code:

void List<T>::reverse(ListNode * & head, ListNode * & tail)
{

    ListNode* t;
    ListNode* curr = head;
    ListNode * funtail = tail;
    int stop=0;
    while(stop==0)
    {
        if(curr==funtail)
        {
            stop = 1;
        }
        t = curr->prev;
        curr->prev = curr->next;
        curr->next = t;
        curr = curr->prev;
    }
    t = tail;
    tail = head;
    head = t;
}

If I start with the list

1 2 3 4 5 6 7 8 9 10

and I pass in pointers to 1 and 4, then the list should look like

4 3 2 1 5 6 7 8 9 10

The problem is, my list returns as just 

1

with the rest of the list lost (well, still accessible from my global tail variable). Any ideas? Is my method wrong?

Upvotes: 1

Views: 3281

Answers (5)

Hussain Pithawala
Hussain Pithawala

Reputation: 469

A simpler solution.

/**
 * Traverses half of the list and swaps a node with another node(
  here by termed as the reflection node)
 * which lies at a position = listSize - (i +1) for every i.
 * Reassignment of element is not needed, hence a soul saver from
 * the copy constructor thing ( '=' assignment operator stuff).
 */
template <typename E> void DLinkedList<E>::reverse(){
    int median = 0;
    int listSize = size();
    int counter = 0;

    if(listSize == 1)
        return;

/**
 * A temporary node for swapping a node and its reflection node
 */
DNode<E>* tempNode = new DNode<E>();

for(int i = 0; i < listSize/2 ; i++){
    DNode<E>* curNode = nodeAtPos(i);
  // A node at 'i'th position
    DNode<E>* reflectionNode = nodeAtPos(listSize - (i + 1));   
 // Reflection of a node considering the same distance from the median

        /**
         * swap the connections from previous and next nodes for current and 
             * reflection nodes
         */
        curNode->prev->next = curNode->next->prev = reflectionNode;

        reflectionNode->prev->next = reflectionNode->next->prev = curNode;

        /**
         * swapping of the nodes
         */
        tempNode->prev = curNode->prev;
        tempNode->next = curNode->next;

        curNode->next = reflectionNode->next;
        curNode->prev = reflectionNode->prev;

        reflectionNode->prev = tempNode->prev;
        reflectionNode->next = tempNode->next;
    }

    delete tempNode;
}

template <typename E> int DLinkedList<E>::size(){
    int count = 0;
    DNode<E>* iterator = head;

    while(iterator->next != tail){
        count++;
        iterator = iterator->next;
    }
    return count;
}

template <typename E> DNode<E>* DLinkedList<E>::nodeAtPos(int pos){
    DNode<E>* iterator = head->next;
    int listSize = size();
    int counter = 0;
    while(counter < pos){
        iterator = iterator->next;
        counter++;
    }

    return iterator;
}

Upvotes: 0

Invictus
Invictus

Reputation: 4328

Your head->prev must be pointing to NULL in first for loop . You better think and implement digramatically it will be helpful . You need t->next->next =t->next.

Upvotes: 0

Irit Katriel
Irit Katriel

Reputation: 3564

If you reverse the segment [first,last], you want first->next set to last->next, not to first->prev, as your code does.

Upvotes: 2

gpr
gpr

Reputation: 485

The problem happens for the first node, since Node 1 prev pointer is NULL and you are assigning it to Node 1's next. You should assign 1's next to Node 5

Upvotes: 0

Jan Koester
Jan Koester

Reputation: 1218

In your method parameters you are mixing "Pointers" with "References".

void List::reverse(ListNode * & head, ListNode * & tail)

Maybe you mean?

void List::reverse(ListNode* head, ListNode* tail)

Upvotes: -1

Related Questions