如何将带随机指针的链表问题改写成长尾词？

本文共计924个文字，预计阅读时间需要4分钟。

“力扣链接+思路一：遍历链表，将链表节点复制下来，控制随机指针指向对应的第几个（相对位置）节点。思路二：以时间换空间，创建两个指针数组，分别存储两个链表中节点地址，直接可“

力扣链接

---

思路一:

遍历链表,将链表结点复制下来,控制随机指针,去找对应的第几个(相对位置)进行链接.

思路二:

以时间换空间,创建两个指针数组,分别存放两个链表中结点的地址,直接可以在指针数组中找到结点

该方法比上面的方法更优,但是时间复杂度依旧很高,但是还是达不到O(N)

思路三:

1.拷贝结点链接在原结点后面

将每个原结点复制,

将复制后得到的结点分别链接到原结点的后面

//1.插入拷贝结点在原结点的后面 struct Node* cur = head; while(cur) { //插入 struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; struct Node* next = cur->next; //链接 cur->next = copy; copy->next = next; cur = next; }

2.拷贝结点的random是原结点random的next

例如:13的random是7,7的random->next是拷贝的7

而拷贝的13的random刚好是拷贝的7

//处理拷贝的结点的random cur = head; while(cur) { struct Node* copy = cur->next; if(cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = cur->next->next; }

3.拷贝结点解下来,连接成一个新链表,原链表恢复

将拷贝的链表尾插成新链表

//拷贝结点解下来,连接成新链表,并且恢复原链表 //这里选择不带哨兵位头结点的尾插 struct Node* copyhead = NULL,*copyTail = NULL;//定义了新链表头copyhead和尾copyTail cur = head; while(cur) { struct Node* copy = cur->next; struct Node* next = copy->next; //copy尾插 if(copyhead == NULL) { copyhead = copyTail = copy; } else { copyTail->next = copy; copyTail = copyTail->next; } //恢复原链表 cur->next = next; cur = next; } return copyhead; }

完整代码:

/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { //1.插入拷贝结点在原结点的后面 struct Node* cur = head; while(cur) { //插入 struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; struct Node* next = cur->next; //链接 cur->next = copy; copy->next = next; cur = next; } //处理拷贝的结点的random cur = head; while(cur) { struct Node* copy = cur->next; if(cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = cur->next->next; } //拷贝结点解下来,连接成新链表,并且恢复原链表 //这里选择不带哨兵位头结点的尾插 struct Node* copyhead = NULL,*copyTail = NULL; cur = head; while(cur) { struct Node* copy = cur->next; struct Node* next = copy->next; //copy尾插 if(copyhead == NULL) { copyhead = copyTail = copy; } else { copyTail->next = copy; copyTail = copyTail->next; } //恢复原链表 cur->next = next; cur = next; } return copyhead; }