商城网站源码免费,宁波网站开发制作,绍兴越城区建设局网站,汕头市道路建设网站方法一#xff1a;暴力求解 1️⃣遍历原链表#xff0c;复制节点尾插 2️⃣更新random#xff0c;原链表中的random对应第几个节点则复制链表中的random就对应第几个 #x1f4d6;Note 不能通过节点中的val判断random的指向#xff0c;因为链表中可能存在两个val相等的节点… 方法一暴力求解 1️⃣遍历原链表复制节点尾插 2️⃣更新random原链表中的random对应第几个节点则复制链表中的random就对应第几个 Note 不能通过节点中的val判断random的指向因为链表中可能存在两个val相等的节点 //创建节点
struct Node* BuyNode(int x)
{struct Node* newnode (struct Node*)malloc(sizeof(struct Node));newnode-val x;newnode-next NULL;return newnode;
}//找到random对应的节点是第几个
int FindRandom(struct Node* head, struct Node* random)
{int count 1;while (head){if (head random){return count;}else {count;head head-next;}}return count;
}struct Node* copyRandomList(struct Node* head) {struct Node* guard (struct Node*)malloc(sizeof(struct Node));guard-next NULL;struct Node* tail guard;struct Node* cur head;//复制原链表while (cur){struct Node* newnode BuyNode(cur-val);tail-next newnode;tail tail-next;cur cur-next;}//tail和cur都指向新链表的头tail guard-next;struct Node* tmp head;//更新randomwhile (tail){//在原链表这种判断random指向的节点是第几个int count FindRandom(head, tmp-random);tmp tmp-next;//更新复制链表中的randomcur guard-next;while (count--){tail-random cur;if (cur){cur cur-next;}}tail tail-next;}struct Node* newhead guard-next;free(guard);return newhead;} 方法二 1️⃣拷贝原节点并链接在原节点之后 2️⃣更新拷贝节点中的random 拷贝节点中的random指向的是原节点中random指向节点的下一个节点 3️⃣将拷贝的节点解下来构成新的复制链表 struct Node* copyRandomList(struct Node* head) {struct Node* cur head;struct Node* copy NULL;//拷贝原节点并链接在原节点之后while (cur){copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;copy-next cur-next;cur-next copy;cur cur-next-next;}//更新拷贝节点的randomcur head;while (cur){copy cur-next;if (cur-random){copy-random cur-random-next;}else{copy-random NULL;}cur cur-next-next;}//将所有拷贝节点解下来构成新链表并恢复原链表结构cur head;struct Node* copyhead, *copytail;copyhead copytail NULL;while (cur){copy cur-next;//取节点尾插if (copytail NULL){copyhead copytail copy;}else{copytail-next copy;copytail copytail-next;}//恢复原链表cur-next copy-next;cur copy-next;}return copyhead;
}
