#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next; //this pointer, will store the address of the next node
Node* prev;
Node(int val) {
data = val;
next = NULL; //NULL means nothing, not pointing to anything
}
};
Node* revLL(Node* head) {
// Initializing three pointers
Node* prev = NULL;
Node* curr = head;
Node* next = NULL;
// Iterating through the linked list
while (curr != NULL) {
// Storing the next node
next = curr->next;
// Updating the next pointer of curr to prev
curr->next = prev;
// Updating prev as curr and curr as next
prev = curr;
curr = next;
}
// prev now points to the new head of the reversed list
return prev;
}
void printLL(Node* node) {
while (node != NULL) {
// So I print the current node value
cout << node->data <<" ";
// Then I move to the next node
node = node->next;
}
cout<<endl;
}
void AddAtEnd(Node* head, int val){
//I want to add a new node, at the end of my LL
// Create a new node
Node* newNode = new Node(val);
// Go to the last node
Node* curr = head;
while(curr->next != NULL) { // because the last element's next will be NULL
curr = curr->next;
}
// Now, It is pointing to the last element
// Point the next of the last node to new node.
curr->next = newNode;
}
int main() {
Node* head = new Node(1);
// head->next = new Node(2);
// head->next->next = new Node(3);
// head->next->next->next = new Node(4);
AddAtEnd(head, 2);
AddAtEnd(head, 3);
AddAtEnd(head, 4);
AddAtEnd(head, 5);
AddAtEnd(head, 6);
cout << "Given linked list: ";
printLL(head);
head = revLL(head);
cout << "Reversed linked list: ";
printLL(head);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBOb2RlIHsKcHVibGljOgoJaW50IGRhdGE7CglOb2RlKiBuZXh0OyAvL3RoaXMgcG9pbnRlciwgd2lsbCBzdG9yZSB0aGUgYWRkcmVzcyBvZiB0aGUgbmV4dCBub2RlCglOb2RlKiBwcmV2OwoJTm9kZShpbnQgdmFsKSB7CgkJZGF0YSA9IHZhbDsKCQluZXh0ID0gTlVMTDsgLy9OVUxMIG1lYW5zIG5vdGhpbmcsIG5vdCBwb2ludGluZyB0byBhbnl0aGluZwoJfQp9OwoKTm9kZSogcmV2TEwoTm9kZSogaGVhZCkgewoJLy8gSW5pdGlhbGl6aW5nIHRocmVlIHBvaW50ZXJzCglOb2RlKiBwcmV2ID0gTlVMTDsKCU5vZGUqIGN1cnIgPSBoZWFkOwoJTm9kZSogbmV4dCA9IE5VTEw7CgoJLy8gSXRlcmF0aW5nIHRocm91Z2ggdGhlIGxpbmtlZCBsaXN0Cgl3aGlsZSAoY3VyciAhPSBOVUxMKSB7CgkJLy8gU3RvcmluZyB0aGUgbmV4dCBub2RlCgkJbmV4dCA9ICBjdXJyLT5uZXh0OwoJCS8vIFVwZGF0aW5nIHRoZSBuZXh0IHBvaW50ZXIgb2YgY3VyciB0byBwcmV2CgkJY3Vyci0+bmV4dCA9IHByZXY7CgkJLy8gVXBkYXRpbmcgcHJldiBhcyBjdXJyIGFuZCBjdXJyIGFzIG5leHQKCQlwcmV2ID0gY3VycjsKCQljdXJyID0gbmV4dDsKCX0KCgkvLyBwcmV2IG5vdyBwb2ludHMgdG8gdGhlIG5ldyBoZWFkIG9mIHRoZSByZXZlcnNlZCBsaXN0CglyZXR1cm4gcHJldjsKfQoKdm9pZCBwcmludExMKE5vZGUqIG5vZGUpIHsKCQoJd2hpbGUgKG5vZGUgIT0gTlVMTCkgewoJCS8vIFNvIEkgcHJpbnQgdGhlIGN1cnJlbnQgbm9kZSB2YWx1ZQoJCWNvdXQgPDwgbm9kZS0+ZGF0YSA8PCIgIjsKCQkvLyBUaGVuIEkgbW92ZSB0byB0aGUgbmV4dCBub2RlCgkJbm9kZSA9IG5vZGUtPm5leHQ7Cgl9Cgljb3V0PDxlbmRsOwp9Cgp2b2lkIEFkZEF0RW5kKE5vZGUqIGhlYWQsIGludCB2YWwpewoJLy9JIHdhbnQgdG8gYWRkIGEgbmV3IG5vZGUsIGF0IHRoZSBlbmQgb2YgbXkgTEwKCQoKCS8vIENyZWF0ZSBhIG5ldyBub2RlCglOb2RlKiBuZXdOb2RlID0gbmV3IE5vZGUodmFsKTsKCgkvLyBHbyB0byB0aGUgbGFzdCBub2RlCglOb2RlKiBjdXJyID0gaGVhZDsKCXdoaWxlKGN1cnItPm5leHQgIT0gTlVMTCkgeyAvLyBiZWNhdXNlIHRoZSBsYXN0IGVsZW1lbnQncyBuZXh0IHdpbGwgYmUgTlVMTAoJCWN1cnIgPSBjdXJyLT5uZXh0OwoJfQoKCS8vIE5vdywgSXQgaXMgcG9pbnRpbmcgdG8gdGhlIGxhc3QgZWxlbWVudAoJLy8gUG9pbnQgdGhlIG5leHQgb2YgdGhlIGxhc3Qgbm9kZSB0byBuZXcgbm9kZS4KCgljdXJyLT5uZXh0ID0gbmV3Tm9kZTsKfQoKaW50IG1haW4oKSB7CglOb2RlKiBoZWFkID0gbmV3IE5vZGUoMSk7CgkvLyBoZWFkLT5uZXh0ID0gbmV3IE5vZGUoMik7CgkvLyBoZWFkLT5uZXh0LT5uZXh0ID0gbmV3IE5vZGUoMyk7CgkvLyBoZWFkLT5uZXh0LT5uZXh0LT5uZXh0ID0gbmV3IE5vZGUoNCk7CgoJQWRkQXRFbmQoaGVhZCwgMik7CglBZGRBdEVuZChoZWFkLCAzKTsKCUFkZEF0RW5kKGhlYWQsIDQpOwoJQWRkQXRFbmQoaGVhZCwgNSk7CglBZGRBdEVuZChoZWFkLCA2KTsKCgljb3V0IDw8ICJHaXZlbiBsaW5rZWQgbGlzdDogIjsKCXByaW50TEwoaGVhZCk7CgoJaGVhZCA9IHJldkxMKGhlYWQpOwoKCWNvdXQgPDwgIlJldmVyc2VkIGxpbmtlZCBsaXN0OiAiOwoJcHJpbnRMTChoZWFkKTsKCglyZXR1cm4gMDsKfQ==