Reverse the elements of a list using pointers

Question

Possible Duplicate:
How to read a singly linked list backwards?
Reverse a LinkedList c++

How can I reverse the elements of a connected list without using arrays

(I have to use only pointers thats my problem).

"I have to use only pointers thats my problem" - raw pointers? Then you're writing C. Regarding your question, if it's a singly linked list, then you can't avoid O(n) complexity, by traversing it once. If it's a doubly linked list, then you can just traverse it in the opposite direction. — Mihai Todor, Nov 02 '12 at 17:50
Maybe [this answer](http://stackoverflow.com/a/13033927/596781) helps... — Kerrek SB, Nov 02 '12 at 17:51
@James He did not show us any code, so I made an assumption. As far as STL is concerned, its containers are type safe and exception safe. Anyway, this is off topic. — Mihai Todor, Nov 02 '12 at 17:59
@MihaiTodor I mean I have to use pointers in order to reverse the list.I have thought of a solution to reverse it but I have to use arrays and I am not allowed to do that.So thats why I am asking for an example on how to do it so I can go on with this exercise. Thanks everyone else for your help I will study the answers you gave me and see what I can make out of it. — MKB, Nov 02 '12 at 18:17

score 1 · Answer 1 · answered Nov 02 '12 at 19:41

You need neither to swap node content or a stack. If you want to reverse a single-linked list just walk it with a pair of pointers plus on intermediate pointer within the iterative loop. Don't forget to update the head pointer when you're finished;

void reverse_list(node **head)
{
    node *cur=NULL, *nxt=NULL;

    if (!(head || *head || (*head)->next))
        return;

    nxt = *head;
    while (nxt != NULL)
    {
        node *prv = cur;
        cur = nxt;
        nxt = nxt->next;
        cur->next = prv;
    }

    *head = cur;
}

Assuming the list node is something like this:

typedef struct node
{
    ..data..
    struct node *next;
} node;

and it is properly managed, then you invoke as such:

node *head = NULL;

...fill the list...

reverse_list(&head);

score 0 · Answer 2 · answered Nov 02 '12 at 17:46

0

Treat the list like a stack, pop the elements off and push them into a new list.

answered Nov 02 '12 at 17:46

SpacedMonkey

2,725
1
16
17

1

I think he would rather do the operation more "in-place", in order to to preserve memory. For this, he will need two auxiliary pointers to the current and previous node, and update the links between the nodes while traversing the list once. – Mihai Todor Nov 02 '12 at 17:52

Anirudha · Answer 3 · 2012-11-02T18:23:44.360

Conside a list called lst which allows us to move forward backward i.e it is doubly linked list

You can reverse the list lst by simply swapping the content of the beginning and the end nodes

void reverse(lst *beg,lst *end)
{
    lst temp;
    while(beg!=end)
    {
        //swap the content of the nodes
        *temp=*beg;
        *beg=*end;
        *end=*temp;

        beg=beg->Next();//move to next node
        end=end->prev();//move to previous node
    }
}

OR

If its a singly linked list,you can use stack

void reverse(lst* beg)
{
    stack<lst*> stc;
    lst* temp=beg;
    lst* temp1=beg;
    while(temp)//store pointers to lst nodes in stack
    {
        stc.push(temp);
        temp=temp.Next();
    }
    while(temp1)//pop the stack by inserting it into list from beginning
    {
       *temp1=*stc.top();
        temp1=temp1.Next(); 
        stc.pop();
    }
}

"Simply use the list container class of c++" - He might not want that, since it is implemented as a doubly linked list, which is not always the best choice for performance-tight code. — Mihai Todor, Nov 02 '12 at 18:02

Reverse the elements of a list using pointers

3 Answers3