Reverse doubly-link list in C++

Question

I've been trying to figure out how to reverse the order of a doubly-linked list, but for some reason, in my function void reverse() runs while loop once and then crashes for some reason. To answer some questions ahead, I'm self-teaching myself with my brothers help. This isn't all of the code, but I have a display() function which prints all nodes chronologically from start_ptr and a switch which activates certain functions like

    case 1 : add_end(); break;
    case 2 : add_begin(); break;
    case 3 : add_index(); break;
    case 4 : del_end(); break;
    case 5 : del_begin(); break;
    case 6 : reverse(); break;

This is the geist of my code:

#include <iostream>
using namespace std;

struct node
{
    char name[20];
    char profession[20];
    int age;
    node *nxt;
    node *prv;
};

node *start_ptr = NULL;

void pswap (node *pa, node *pb)
{
    node temp = *pa;
    *pa = *pb;
    *pb = temp;
    return;
}

void reverse()
{
    if(start_ptr==NULL)
    {
        cout << "Can't do anything" << endl;
    }
    else if(start_ptr->nxt==NULL)
    {
        return;
    }
    else
    {
        node *current = start_ptr;
        node *nextone = start_ptr;
        nextone=nextone->nxt->nxt;
        current=current->nxt;
        start_ptr->prv=start_ptr->nxt;
        start_ptr->nxt=NULL;
        //nextone=nextone->nxt;
        while(nextone->nxt!= NULL)
        {
            pswap(current->nxt, current->prv);
            current=nextone;
            nextone=nextone->nxt;
        }
        start_ptr=nextone;
    }
}

Answer 1

Your pswap function is wrong your should swap the pointer not try to create temporary objects and swap them. Should be like that (there might be other mistake later)

void pswap (node *&pa, node *&pb)
{
    node* temp = pa;
    pa = pb;
    pb = temp;
    return;
}

Answer 2

Look at

valuesnextone=nextone->nxt->nxt;

Here nextone->nxt can be null.

Apart from that, try to use pointers to pointers in the swap function.

Answer 3

Simple solution. reverses in less than half a number of total iterations over the list

template<typename E> void DLinkedList<E>::reverse() {
    int median = 0;
    int listSize = size();
    int counter = 0;

    if (listSize == 1)
    return;

    DNode<E>* tempNode = new DNode<E>();

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

    DNode<E>* headCursor = head;
    DNode<E>* tailCursor = tail;

    for (int i = 0; i < listSize / 2; i++) {
        cout << i << "\t";

        headCursor = headCursor->next;
        tailCursor = tailCursor->prev;

        DNode<E>* curNode = headCursor;
        DNode<E>* reflectionNode = tailCursor;

        if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
            /**
             * insert a dummy node for reflection
         * for even sized lists
         */
        curNode->next = dummyNode;
        dummyNode->prev = curNode;

        reflectionNode->prev = dummyNode;
        dummyNode->next = reflectionNode;

    }
    /**
     * 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;

    if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
        /**
         * remove a dummy node for reflection
         * for even sized lists
         */
        reflectionNode->next = curNode;
        curNode->prev = reflectionNode;
    }

    /**
     * Reassign the cursors to position over the recently swapped nodes
     */
        tailCursor = curNode;
        headCursor = reflectionNode;

    }

    delete tempNode, dummyNode;
}

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

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

Answer 4

My code for reversing doubly linked list,

Node* Reverse(Node* head)
{
// Complete this function
// Do not write the main method. 


if(head != NULL) {

    Node* curr = head;
    Node* lastsetNode = curr;
    while(curr != NULL) {

        Node* frwdNode = curr->next;
        Node* prevNode = curr->prev;


        if(curr==head) {                
            curr->next = NULL;
            curr->prev = frwdNode;
            lastsetNode = curr;
        }
        else {
            curr->next = lastsetNode;
            curr->prev = frwdNode;
            lastsetNode = curr;
        }



        curr = frwdNode;
    }

    head = lastsetNode;
}


return head;
}

Answer 5

Try this:

node *ptr = start_ptr;
while (ptr != NULL) {
    node *tmp = ptr->nxt;
    ptr->nxt = ptr->prv;
    ptr->prv = tmp;
    if (tmp == NULL) {
        end_ptr = start_ptr;
        start_ptr = ptr;
    }
    ptr = tmp;
}

Answer 6

EDIT: My first implementation, which was correct but not perfect. Your implementation is pretty complicated. Can you try this instead:

node * reverse(Node * start_ptr)
{
    Node *curr = start_ptr; 
    Node * prev = null;
    Node * next = null;
    while(curr)
    {
        next = curr->nxt;
        curr->nxt = prev;
    curr->prv = next;
        prev = curr;
        curr = next;
    }
    return start_ptr=prev;
}

Here is my updated solution:

node * reverse()
{
    node *curr = start_ptr; 
    node * prev = NULL;
    node * next = NULL;
    while(curr)
    {
        next = curr->nxt;
        curr->nxt = prev;
        curr->prv = next;
        prev = curr;
        curr = next;
    }
    return start_ptr=prev;
}

The logic was correct. But the issue was that I was accepting in input argument start_ptr. Which means that I was returning the local copy of it. Now it should be working.