reverse order of linked list by push

Question

i am trying to make a function that changes the order of the pointers of the nodes so that the original list is reversed.

my solution is based on iterating over the main list, then reversing the order of each 2 adjacent nodes: (n1)->(n2) would be (n1)<-(n2) after the first iteration.

my try:

Node push1(Node* curr) {
    if(curr == NULL || *curr == NULL) {
        return NULL;
    }
    Node temp = (*curr)->next;
    if(temp == NULL) {
        return NULL;
    }
    (*curr)->next = *curr;
    return temp;
}
/*******************************/
void reverse2(Node* head) {
    Node curr = *head;
    while(curr != NULL) {
        curr = push1(&curr);
    }
}

PROBLEM: i ran through an infinity loop. i tried to fix that but then the list didn't reverse order. is there a way using this approach of push1() that could work?

NOTE: i am not seeking the solution with 3 pointers or recursion.

the 3 pointer solution is simple, elegant and trivial to verify for correctness. please elaborate why you reject it — sp2danny, Feb 19 '15 at 15:34
`(*curr)->next = *curr;` makes all the elements point to themselves in little loops, next time you process the list it will loop forever. — ryanpattison, Feb 19 '15 at 15:38
**rpattiso**, yes i know, it creates a node that points to itself wich generates the infinty loop i got. I am looking for a way to get over that.. **sp2danny**, looking for new ways of doing things make you more professional..i agree with u that the 3 ptr solution is elegant, but not enough. — ThunderWiring, Feb 19 '15 at 15:39
@ThunderWiring (use"@" before the username to reply) , see [How To reverse a singly liked list using two pointers](http://stackoverflow.com/questions/1801549/how-to-reverse-a-singly-linked-list-using-only-two-pointers) — ryanpattison, Feb 19 '15 at 15:45
So, after you swap the direction of the first pair of nodes, it sounds like you will have `(n1)<-(n2) (n3)->(n4)->(n5)`. That is, you've lost access to `n3`, `n4`, and `n5`. Could you explain how you are planning on dealing with that? The normal solution to this problem is __using three pointers__. — Bill Lynch, Feb 19 '15 at 15:46
Also, either your code doesn't compile __at all__ or Node is a typedef for `struct Node_Obj *`? And then you're passing double pointers all over the place? — Bill Lynch, Feb 19 '15 at 15:49
@ Bill Lynch, yes, Node is a `typedef` which is a pointer to the node struct itself(that contains data and next). If you look in function `push1` there is a returned `temp` variable that holds the value of `current->next` thus, you can't loose the rest of the list — ThunderWiring, Feb 19 '15 at 15:52

score 1 · Answer 1 · answered Feb 19 '15 at 15:59

1

This works, but is a bit silly

Node* push1(Node** prev, Node* curr)
{
    Node* ret = curr->next;
    curr->next = *prev;
    (*prev)=curr;
    return ret;
}

void reverse2(Node** head)
{
    Node* prev = *head;
    if(!prev) return;
    Node* curr = prev->next;
    if(!curr) return;
    prev->next = 0;
    while(curr)
    {
        curr = push1(&prev,curr);
    }
    *head = prev;
}

answered Feb 19 '15 at 15:59

sp2danny

7,488
3
31
53

this assumes `Node` is a typedef for the struct, not a pointer to it – sp2danny Feb 19 '15 at 16:02
that is fairly close to what i am trying to do..so basically it is a variation of the 3 pointers approach. Thank you for posting this! – ThunderWiring Feb 19 '15 at 16:15

Bruce Dean · Answer 2 · 2015-02-19T18:12:21.720

This is fairly easy using a std::stack<> data structure in combination with a std::vector<>. Recall that Stacks are a type of container, designed to operate in a LIFO context (last-in first-out), where the elements are inserted and extracted only from one end of the container.

So in your situation you will create a stack, add your nodes to the stack in the order you already have, then popping them back off the stack reverses the order of the nodes.

I have sketched the code to do this but note that it is not tested, you should be able to adapt this idea to you situation:

#include <stack>
#include <vector>

std::vector<Node> reverseNodes(Node* currNode, Node* startNode) {
    std::vector<Node> reversed;
    std::stack<Node> nodeStack;

    // First add nodes to the stack:
    for (Node* aNode = currNode; aNode != startNode; aNode = aNode->next) {
        nodeStack.push(aNode);
    }

    // Next add your starting node to the stack (last-in):
    nodeStack.push(startNode);

    // Popping off of the stack reverses the order:
    while (!nodeStack.empty()) {
        reversed.push_back(nodeStack.pop());
    }

    // Return the nodes ordered from last->first:
    return reversed;
}

This is actually very similar to recursion. The call stack has just been replaced with another stack on the data heap. — Adam Sosnowski, Feb 19 '15 at 17:09

Adam Sosnowski · Answer 3 · 2015-02-19T17:17:43.477

This is not readable or portable but it does not use recursion or additional variables:

struct list {
    list *next;
    /* ... */
};


list *
reverse(list *l)
{
    list *head = nullptr;

    while (l) {
         head    = (list *) ((uint64_t) head    ^ (uint64_t) l->next);
         l->next = (list *) ((uint64_t) l->next ^ (uint64_t) head);
         head    = (list *) ((uint64_t) head    ^ (uint64_t) l->next);

         l    = (list *) ((uint64_t) l    ^ (uint64_t) head);
         head = (list *) ((uint64_t) head ^ (uint64_t) l);
         l    = (list *) ((uint64_t) l    ^ (uint64_t) head);
    }

    return head;
}

The trick is to use xor swaps.

Yeah! I don't imagine writing it otherwise than in response to this question :) — Adam Sosnowski, Feb 23 '15 at 19:23

reverse order of linked list by push

3 Answers3