CODEWITHSUNDEEP
c++listalgorithmlinked-list
user15216527
user15216527

Reputation:

Reverse a linked list, is my idea correct?

I was reading this: https://www.geeksforgeeks.org/reverse-a-linked-list/

I think I found an easier answer but since it wasn't written their and they used more complicated one I think something is wrong with mine and can't figure it out.

We start from the first node which we will copy and insert it into a new list. then we go one step to the right, copy the value, create a new list with that value and setting its right the previous list and so on.

What's wrong with my algorithm?

Upvotes: 1

Views: 85

Answers (2)

Ted Lyngmo
Ted Lyngmo

Reputation: 117318

If I interpret your idea correctly, it is something like this:

void forward_list::reverse() {
    forward_list new_list;

    for(auto& v : *this)
        new_list.emplace_front(std::move(v));

    std::swap(new_list, *this);   // or *this = std::move(new_list);
}

... and this would work. It even looks pretty nice I'd say.

What's wrong with my algorithm?

  • It's creates a new node for every old node and then has to copy/move the data from the old node to the new node. The old nodes will then be destroyed.
  • Some types aren't even copyable or moveable so this reverse algorithm couldn't be used with such types.
  • It invalidates references and iterators.

Consider the alternative, reversing the links. It's a bit more complex but gets the job done without any of the drawbacks mentioned above.

Here's my take on reversing the links, which is not implemented exactly the same way as in the link you shared but it works pretty much in the same way. I think this one has fewer assignments though.

curr will point one step ahead of head and next is used to save the next pointer when the relinking is being done.

void forward_list::reverse() {
    if(head) {                               // must have at least one node
        node* curr = head->next;             // head + 1
        head->next = nullptr;                // this will be the new last node
        node* next;                          // for saving next while relinking
        while(curr) {                        // while curr != nullptr
            next = curr->next;               // save the next pointer
            curr->next = head;               // relink backwards
            head = curr;                     // move head forward
            curr = next;                     // move curr forward
        }
        // head now points at the new start of the list automatically
    }
}

Upvotes: 2

Nick Reed
Nick Reed

Reputation: 5059

Your algorithm is functionally correct, but since you are creating an entirely new list instead of reversing the existing nodes in-place, you are using twice the memory. You also have to deal with the cleanup of deleting the old nodes once you have your new list.

Upvotes: 1

Related Questions