2

How to reverse linked list using double pointer?

I was learning about double pointers and thought if we can reverse linked list using one pointer only.

5
  • By "double pointer" do you mean a pointer-to-a-pointer-to-a-Node (e.g. Node **) or do you mean having two pointer values (Node *) per Node object? Commented Sep 1, 2020 at 3:32
  • pointer to pointer Commented Sep 1, 2020 at 3:34
  • Singly linked list or doubly-linked? Commented Sep 1, 2020 at 3:39
  • One important lesson to learn about pointers-to-pointers is to not use them. (They are used more often than they should. As in they are used and rarely should be.) Did your lessons get this far? :) Commented Sep 1, 2020 at 3:44
  • If the linked list is singly linked then you can't iterate backward. The current node only knows about the next node. It doesn't have any information to tell it where the previous node just was. Commented Sep 1, 2020 at 4:08

1 Answer 1

1

Conversion to using a pointer to pointer left as an exercise for the reader. Also has some distinct shortcomings in terms of style.

#include <iostream>

struct node { 
    int data;
    node *next;
};

node *reverse(node *list) { 
    node *prev = NULL;
    node *next;

    while (list) {
        next = list->next;
        list->next = prev;
        prev = list;
        list = next;
    }
    return prev;
}

void show_list(node *list) {
    while (list != NULL) {
        std::cout << list->data << ", ";
        list = list->next;
    }
}

int main() {
    node *list = NULL;

    for (int i=0; i<10; i++) {
        node *n = new node;
        n->next = list;
        n->data = i;
        list = n;
    }

    std::cout << "As built: ";
    show_list(list);

    list = reverse(list);

    std::cout << "Reversed: ";
    show_list(list);
    return 0;
}

If you decide to modify a pointer you received as a parameter, it's probably easier to deal with a reference to a pointer than a pointer to a pointer though.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.