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

You're swapping the contents of the nodes rather than just the node pointers. Are you sure you want to do that? — Marius Gedminas
– Marius Gedminas, Commented Jul 7, 2010 at 20:43
On a related note, you could look at the things from a different point of view. Rather than reverse the contents of the doubly-linked list itself, you could instead focus on iterating over the contents of the list in reverse, which should be straightforward since the list is doubly-linked. For example, implement STL-style bidirectional iterators for your list. They can be used with the std::reverse_iterator<> adapter (for rbegin() and rend()). Once those methods are implemented it'll be simple to leverage the STL algorithms, including std::reverse(). It's a fun exercise, IMO. — Void - Othman
– Void - Othman, Commented Jul 7, 2010 at 23:42

Borealid · Accepted Answer · 2010-07-07 20:41:03Z

7

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

answered Jul 7, 2010 at 20:41

Borealid

99.4k9 gold badges112 silver badges124 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Dan Over a year ago

Best one, though I'm having a brain fart because you didn't end the list with the pointer addressed to NULL

Dan Over a year ago

Wow, thanks a lot man, I fixed your code up a bit and it looks so much prettier than all my other attempts. All you had to do was add a qualification when start_ptr==NULL || start_ptr->nxt==NULL and make your part of the code the else end. Within that, I made sure at the end code, end_ptr->nxt=NULL; Thanks a bunch

Borealid Over a year ago

I'm not really sure why you need those checks - I think the code I gave will work fine without them. And at the end, end_ptr->nxt will be NULL because at the start, start_ptr->prv was NULL. But you're welcome, at any rate.

roottraveller Over a year ago

@Borealid can't we just assign head pointer to the last node and NULL to prv of starting node?

einpoklum Over a year ago

@Dan : I know 9 years have passe, but - end_ptr is not defined anywhere. Did you make that change?

bits · Accepted Answer · 2010-07-07 22:10:14Z

3

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.

edited Jul 7, 2010 at 22:10

answered Jul 7, 2010 at 20:45

bits

8,4109 gold badges49 silver badges57 bronze badges

2 Comments

bits Over a year ago

I just can't figure out how I might be doing that. Can anyone confirm if this implementation creates a circular linked list? Thanks...

bits Over a year ago

Hi Danutenshu, I have updated my solution. I know your issues is already solved, but I would feel much better if you can please let me know if what I have changed is correct?

Justin Ardini · Accepted Answer · 2010-07-11 17:45:17Z

2

You can simplify your reverse() quite a bit. I'd do something like this:

void reverse()
{
    if(start_ptr == NULL)
    {
        cout << "Can't do anything" << endl;
    }
    else
    {
        node *curr = start_ptr;
        while(curr != NULL)
        {
            Node *next = curr->next;
            curr->next = curr->prev;
            curr->prev = next;
            curr = next;
        }
        start_ptr = prev;       
    }
}

Explanation: The basic idea is simply to visit each Node and swap the links to previous and next. When we move curr to the next Node, we need to store the next node so we still have a pointer to it when we set curr.next to prev.

edited Jul 11, 2010 at 17:45

answered Jul 7, 2010 at 20:42

Justin Ardini

9,9062 gold badges41 silver badges46 bronze badges

2 Comments

Borealid Over a year ago

I think you missed updating the first node's prev to be the second node.

Justin Ardini Over a year ago

Indeed, and I was off-by-one at the start. Should be better now.

Hussain Pithawala · Accepted Answer · 2013-01-21 11:10:41Z

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

Thomas Matthews · Accepted Answer · 2010-07-07 20:46:23Z

0

I suggest maintaining a link to the last node.
If not, find the last node. Traverse the list using the "previous" links (or in your case, prv).

There is no need to actually change the links around. Traversing using the prv pointer will automatically visit the nodes in reverse order.

answered Jul 7, 2010 at 20:46

Thomas Matthews

58.1k18 gold badges105 silver badges165 bronze badges

Comments

Diego Pereyra · Accepted Answer · 2010-07-07 20:46:35Z

0

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.

answered Jul 7, 2010 at 20:46

Diego Pereyra

4173 silver badges10 bronze badges

Comments

mb14 · Accepted Answer · 2010-07-07 20:59:23Z

0

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

edited Jul 7, 2010 at 20:59

answered Jul 7, 2010 at 20:45

mb14

22.7k9 gold badges63 silver badges107 bronze badges

2 Comments

SoapBox Over a year ago

That won't actually do anything. You need to pass pointers to pointers or references to pointers so the changes apply to the original objects, not local copies.

mb14 Over a year ago

you are absolutely right, I didn't look at the signature function. Just fixed the temporary object creation mistake

Jyo the Whiff · Accepted Answer · 2015-12-30 09:19:53Z

0

A very simple and O(n) solution using two pointers:

start = head of the doubly LL

struct node *temp, *s;
s = start;

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

//if list has more than one node
if(current != NULL){
  start = temp->prev;
}

answered Dec 30, 2015 at 9:19

Jyo the Whiff

8592 gold badges9 silver badges24 bronze badges

Comments

Ashish · Accepted Answer · 2016-04-14 08:14:00Z

0

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

answered Apr 14, 2016 at 8:14

Ashish

4071 gold badge5 silver badges13 bronze badges

Comments

einpoklum · Accepted Answer · 2019-11-20 15:42:22Z

0

I thought I'd add a recursive solution here.

node* reverse_and_get_new_head(node* head) {
    if (head == nullptr) { return nullptr; } 
      // This can be avoided by ensuring the initial,
      // outer call is with a non-empty list
    std::swap(head->prev, head->next);
    if (head->prev == nullptr) { return head; }
    return reverse_and_get_new_head(head->prev);
}

void reverse() {
    start_ptr = reverse_and_get_new_head(start_ptr);
}

edited Nov 20, 2019 at 15:42

answered Nov 17, 2019 at 20:45

einpoklum

137k86 gold badges445 silver badges917 bronze badges

Collectives™ on Stack Overflow

Reverse doubly-link list in C++

10 Answers 10

5 Comments

2 Comments

2 Comments

Comments

Comments

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

10 Answers 10

5 Comments

2 Comments

2 Comments

Comments

Comments

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related