// Given the head to a singly linked list, where each node also has a “random” pointer
// that points to anywhere in the linked list, deep clone the list.
#include <iostream>
using namespace std;
class Node {
public:
Node(int data, Node* next = nullptr)
{
setNext(next);
setData(data);
}
void setNext(Node* newNext) { next = newNext; }
void setData(int newData) { data = newData; }
Node* getNext() { return next; }
int getData() { return data; }
private:
Node* next = nullptr;
int data = 0;
};
Node* CopyList(Node* og)
{
Node* copyHead = new Node(og->getData());
Node* copyNode = copyHead;
Node* ogNode = og->getNext();
while (ogNode)
{
Node* newNode = new Node(ogNode->getData());
copyNode->setNext(newNode);
ogNode = ogNode->getNext();
copyNode = copyNode->getNext();
}
return copyHead;
}
void printList(Node* head)
{
Node* temp = head;
while (temp)
{
cout << temp->getData() << ", ";
temp = temp->getNext();
}
cout << endl;
}
int main()
{
Node* head1 = new Node(9);
Node* node1 = new Node(3, nullptr);
head1->setNext(node1);
Node* node2 = new Node(1, nullptr);
node1->setNext(node2);
Node* node3 = new Node(6, nullptr);
node2->setNext(node3);
printList(head1);
auto result = CopyList(head1);
printList(result);
return 0;
}
Commenti