CODEWITHSUNDEEP
c++clist
ThunderWiring
ThunderWiring

Reputation: 738

reverse order of linked list by push

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.

Upvotes: 0

Views: 251

Answers (3)

Bruce Dean
Bruce Dean

Reputation: 2828

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

Upvotes: 1

Adam Sosnowski
Adam Sosnowski

Reputation: 1294

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.

Upvotes: 1

sp2danny
sp2danny

Reputation: 7687

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

Upvotes: 1

Related Questions