// reversing a linked list using recursion method
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
Node* reverse(Node* head)
{
if (head == NULL || head->next == NULL)
return head;
Node* rest = reverse(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
void print()
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data)
{
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main()
{
LinkedList wave;
wave.push(1);
wave.push(2);
wave.push(3);
wave.push(4);
wave.push(5);
wave.push(6);
wave.push(7);
wave.push(8);
cout << "Given linked list is:\n";
wave.print();
wave.head = wave.reverse(wave.head);
cout << "\nReversed linked list is: \n";
wave.print();
return 0;
}
Ly8gcmV2ZXJzaW5nIGEgbGlua2VkIGxpc3QgdXNpbmcgcmVjdXJzaW9uIG1ldGhvZCAKI2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IE5vZGUgewogICAgaW50IGRhdGE7CiAgICBzdHJ1Y3QgTm9kZSogbmV4dDsKICAgIE5vZGUoaW50IGRhdGEpCiAgICB7CiAgICAgICAgdGhpcy0+ZGF0YSA9IGRhdGE7CiAgICAgICAgbmV4dCA9IE5VTEw7CiAgICB9Cn07CnN0cnVjdCBMaW5rZWRMaXN0IHsKICAgIE5vZGUqIGhlYWQ7CiAgICBMaW5rZWRMaXN0KCkgeyBoZWFkID0gTlVMTDsgfQoKICAgIE5vZGUqIHJldmVyc2UoTm9kZSogaGVhZCkKICAgIHsKICAgICAgICBpZiAoaGVhZCA9PSBOVUxMIHx8IGhlYWQtPm5leHQgPT0gTlVMTCkKICAgICAgICAgICAgcmV0dXJuIGhlYWQ7CiAgICAgICAgICAgIAogICAgICAgIE5vZGUqIHJlc3QgPSByZXZlcnNlKGhlYWQtPm5leHQpOwogICAgICAgIGhlYWQtPm5leHQtPm5leHQgPSBoZWFkOwoKICAgICAgICBoZWFkLT5uZXh0ID0gTlVMTDsKICAgICAgICByZXR1cm4gcmVzdDsKICAgIH0KICAgIAogICAgdm9pZCBwcmludCgpCiAgICB7CiAgICAgICAgc3RydWN0IE5vZGUqIHRlbXAgPSBoZWFkOwogICAgICAgIHdoaWxlICh0ZW1wICE9IE5VTEwpIHsKICAgICAgICAgICAgY291dCA8PCB0ZW1wLT5kYXRhIDw8ICIgIjsKICAgICAgICAgICAgdGVtcCA9IHRlbXAtPm5leHQ7CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgcHVzaChpbnQgZGF0YSkKICAgIHsKICAgICAgICBOb2RlKiB0ZW1wID0gbmV3IE5vZGUoZGF0YSk7CiAgICAgICAgdGVtcC0+bmV4dCA9IGhlYWQ7CiAgICAgICAgaGVhZCA9IHRlbXA7CiAgICB9Cn07CgppbnQgbWFpbigpCnsKICAgIExpbmtlZExpc3Qgd2F2ZTsKICAgIHdhdmUucHVzaCgxKTsKICAgIHdhdmUucHVzaCgyKTsKICAgIHdhdmUucHVzaCgzKTsKICAgIHdhdmUucHVzaCg0KTsKICAgIHdhdmUucHVzaCg1KTsKICAgIHdhdmUucHVzaCg2KTsKICAgIHdhdmUucHVzaCg3KTsKICAgIHdhdmUucHVzaCg4KTsKCiAgICBjb3V0IDw8ICJHaXZlbiBsaW5rZWQgbGlzdCBpczpcbiI7CiAgICB3YXZlLnByaW50KCk7CgogICAgd2F2ZS5oZWFkID0gd2F2ZS5yZXZlcnNlKHdhdmUuaGVhZCk7CgogICAgY291dCA8PCAiXG5SZXZlcnNlZCBsaW5rZWQgbGlzdCBpczogXG4iOwogICAgd2F2ZS5wcmludCgpOwogICAgcmV0dXJuIDA7Cn0K