#include <iostream>
// For simplicity, keeping everything public
template<class T>
class Node
{
public:
Node(T data) : data(data), prev(nullptr), next(nullptr) {}
T data;
Node* prev;
Node* next;
};
template<class T>
class MyLinkedList
{
public:
Node<T>* head;
Node<T>* tail;
MyLinkedList() : head(nullptr), tail(nullptr) {}
void Add(T data)
{
Node<T>* newData = new Node<T>(data);
if(head == nullptr) { head = tail = newData; }
else
{
newData->prev = tail;
tail->next = newData;
tail = newData;
}
}
void Print()
{
Node<int>* ptr = head;
while(ptr != nullptr)
{
std::cout << ptr->data << "\n";
ptr = ptr->next;
}
}
void Reverse()
{
// How would you implement this in O(1)?
std::swap(head, tail);
}
};
int main() {
MyLinkedList<int> list;
for(int i = 1; i <= 10; ++i) list.Add(i);
list.Print();
std::cout << "\nSwapping the list...\n";
list.Reverse();
list.Print();
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKLy8gRm9yIHNpbXBsaWNpdHksIGtlZXBpbmcgZXZlcnl0aGluZyBwdWJsaWMKdGVtcGxhdGU8Y2xhc3MgVD4KY2xhc3MgTm9kZQp7CnB1YmxpYzoKICBOb2RlKFQgZGF0YSkgOiBkYXRhKGRhdGEpLCBwcmV2KG51bGxwdHIpLCBuZXh0KG51bGxwdHIpIHt9CiAgCiAgVCBkYXRhOwogIE5vZGUqIHByZXY7CiAgTm9kZSogbmV4dDsKfTsKCnRlbXBsYXRlPGNsYXNzIFQ+CmNsYXNzIE15TGlua2VkTGlzdAp7CnB1YmxpYzoKICBOb2RlPFQ+KiBoZWFkOwogIE5vZGU8VD4qIHRhaWw7CiAgCiAgTXlMaW5rZWRMaXN0KCkgOiBoZWFkKG51bGxwdHIpLCB0YWlsKG51bGxwdHIpIHt9CiAgCiAgdm9pZCBBZGQoVCBkYXRhKQogIHsKICAJTm9kZTxUPiogbmV3RGF0YSA9IG5ldyBOb2RlPFQ+KGRhdGEpOwogIAkKICAJaWYoaGVhZCA9PSBudWxscHRyKSB7IGhlYWQgPSB0YWlsID0gbmV3RGF0YTsgfQogIAllbHNlIAogIAl7CiAgCQluZXdEYXRhLT5wcmV2ID0gdGFpbDsKICAJCXRhaWwtPm5leHQgPSBuZXdEYXRhOwogIAkJdGFpbCA9IG5ld0RhdGE7CiAgCX0KICB9CiAgCiAgdm9pZCBQcmludCgpCiAgewogIAlOb2RlPGludD4qIHB0ciA9IGhlYWQ7Cgl3aGlsZShwdHIgIT0gbnVsbHB0cikKCXsKCQlzdGQ6OmNvdXQgPDwgcHRyLT5kYXRhIDw8ICJcbiI7CgkJcHRyID0gcHRyLT5uZXh0OwoJfQogIH0KICAKICB2b2lkIFJldmVyc2UoKQogIHsKICAJLy8gSG93IHdvdWxkIHlvdSBpbXBsZW1lbnQgdGhpcyBpbiBPKDEpPwogIAlzdGQ6OnN3YXAoaGVhZCwgdGFpbCk7CiAgfQp9OwoKaW50IG1haW4oKSB7CglNeUxpbmtlZExpc3Q8aW50PiBsaXN0OwoJZm9yKGludCBpID0gMTsgaSA8PSAxMDsgKytpKSBsaXN0LkFkZChpKTsKCWxpc3QuUHJpbnQoKTsKCQoJc3RkOjpjb3V0IDw8ICJcblN3YXBwaW5nIHRoZSBsaXN0Li4uXG4iOwoJbGlzdC5SZXZlcnNlKCk7CgkKCWxpc3QuUHJpbnQoKTsKCQoJcmV0dXJuIDA7Cn0=