【leetcode】138.复制带随机指针的链表

方法一：暴力求解

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;
}