牛客网《剑指Offer》 编程 25.复杂链表的复制 （最优解法）

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

这次使用时间复杂度为O(n)，空间复杂度为O(1)的算法。

首先，在原链表的每个节点后面复制相应的链表节点，即复制next域。

然后，复制random域。原链表中某个节点的random域的下一个节点，就是复制链表的random域。

最后，将链表拆分成为两个链表。奇数位上的是原链表节点，偶数位上的是复制链表节点。

代码实现

RandomListNode* Clone(RandomListNode* pHead) { if (pHead == nullptr) { return nullptr; } RandomListNode* currNode = pHead; RandomListNode* newNode = nullptr, *newHead = nullptr, *preNode = nullptr; //第一次遍历链表，将与原链表节点值相同的信链表节点放在对应的原链表节点后面。 while (currNode) { newNode = new RandomListNode(currNode->label); newNode->next = currNode->next; currNode->next = newNode; currNode = newNode->next; } currNode = pHead; newHead = currNode->next; newNode = currNode->next; //第二次遍历，复制random域。 while (currNode&&newNode) { RandomListNode* currRandom = currNode->random; if (currRandom) { RandomListNode* randomNode = currRandom->next; newNode->random = randomNode; } currNode = newNode->next; newNode = currNode->next; } //第三次遍历，拆分链表。奇数位上的是原链表的节点，偶数位上的是复制链表的节点。 currNode = pHead; newNode = currNode->next; while (currNode&&newNode) { currNode->next = newNode->next; currNode = currNode->next; if (currNode) { newNode->next = currNode->next; newNode = newNode->next; } } return newHead; }

测试用例

打印函数如下所示：先按照顺序打印出链表的next域，然后打印出链表的的radom域。

使用五个测试用例：

1.空链表

2.普通复杂链表

3.random域指向自身的链表

4.只有一个节点的链表

5.存在护指节点的链表

void print(RandomListNode* head) {//打印函数 RandomListNode* temp = head; while (temp) { cout << temp->label << "->"; temp = temp->next; } cout << "null"; cout << endl; temp = head; while (temp) { if (temp->random == nullptr) { cout << temp->label << "=>" << "null" << endl; } else { cout << temp->label << "=>" << temp->random->label << endl; } temp = temp->next; } } int main() { //Test1:空链表 RandomListNode* node = nullptr; //Test2:普通随机链表 RandomListNode* node0 = new RandomListNode(0); RandomListNode* node1 = new RandomListNode(1); RandomListNode* node2 = new RandomListNode(2); RandomListNode* node3 = new RandomListNode(3); RandomListNode* node4 = new RandomListNode(4); node0->next = node1; node1->next = node2; node2->next = node3; node3->next = node4; node4->next = nullptr; node0->random = node2; node1->random = node4; node3->random = node1; //Test3:random域指向自身 RandomListNode* node5 = new RandomListNode(5); RandomListNode* node6 = new RandomListNode(6); node5->next = node6; node6->next = nullptr; node5->random = node5; //Test4:只有一个节点的链表 RandomListNode* node7 = new RandomListNode(7); node7->next = nullptr; node7->random = node7; //Test5:两个链表节点互相指，从而形成环状 RandomListNode* node8 = new RandomListNode(8); RandomListNode* node9 = new RandomListNode(9); RandomListNode* node10 = new RandomListNode(10); RandomListNode* node11 = new RandomListNode(11); RandomListNode* node12= new RandomListNode(12); node8->next = node9; node9->next = node10; node10->next = node11; node11->next = node12; node12->next = nullptr; node9->random = node11; node11->random = node9; //判断是否是值相同的链表：先打印链表，再打印每个节点的random域。 cout << "******************Test1:空链表测试******************" << endl; RandomListNode* ans = Clone(node); cout << "原链表:" << endl; print(node); cout << endl; cout << "复制链表:" << endl; print(ans); cout << "******************Test2:空链表测试******************" << endl; RandomListNode* ans0 = Clone(node0); cout << "原链表:" << endl; print(node0); cout << endl; cout << "复制链表:" << endl; print(ans0); cout << "******************Test3:random域指向自身链表测试******************" << endl; RandomListNode* ans1 = Clone(node5); cout << "原链表:" << endl; print(node5); cout << endl; cout << "复制链表:" << endl; print(ans1); cout << "******************Test4:只有一个节点的链表测试******************" << endl; RandomListNode* ans2 = Clone(node7); cout << "原链表:" << endl; print(node7); cout << endl; cout << "复制链表:" << endl; print(ans2); cout << "******************Test5:存在两个节点护指的链表测试******************" << endl; RandomListNode* ans3 = Clone(node8); cout << "原链表:" << endl; print(node8); cout << endl; cout << "复制链表:" << endl; print(ans3); return 0; }

测试结果