问题描述小编学习了这么久单链表感觉自我良好,想着刷道题测试一下,看到了一个中等难度的题目,小编想着尝试一下,结果被瞬间打脸!读懂题目都花了好长时间,思路更是断断续续的,结合题解并研究了一段时间后,把这道题目的解析分享给大家。
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。
总的来说就是让你把链表拷贝一份,与以往不同的是,多了一个随机指针random,需要判断random的指向。
先把原链表每个结点拷贝下来,再去判断random的指向,这个时候的时间复杂度就比较高了,拷贝原链表是O(n),判断random指向的时候,最坏的情况每个random都指向最后一个,经典的O(n^2)。
思路二:分步走:
①在原链表的基础上,在每个节点的后面,复制前面的结点,并将其与原链表链接。
②判断随机指针random的指向。
③将拷贝的结点从原链表中分离出来,返回新链表的指针。
该思路时间复杂度为O(n).
第一步:在原链表上复制链表
第二步:判断random指向(问题的关键)
红色线代表random指向
第三步:分离链表(利用哨兵位尾插)
下面结合代码深入理解一下
//在每个源节点的后面创建一个拷贝结点
struct Node* cur=head;
while(cur){struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
struct Node* next=cur->next;
newnode->val=cur->val;
//链接拷贝的结点
cur->next=newnode;
newnode->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;
}
//将拷贝的链表分离出来
cur=head;
struct Node* rhead,*tail;
rhead=tail=(struct Node*)malloc(sizeof(struct Node));
rhead->next=NULL;
while(cur){struct Node* copy=cur->next;
struct Node* next=copy->next;
//保护原链表结构
cur->next=next;
//分离出新链表
tail->next=copy;
tail=tail->next;
cur=next;
}
tail->next=NULL;
struct Node* new=rhead->next;
free(rhead);
return new;
总结本题的难度一是思路难,二是代码编写困难,需要根据图分析相对联系,比如:分析random指向的时候,需要(copy->random=cur->random->next;),拷贝结点的random要指向原节点random指向节点的下一个哦。理清思路,反复思考是解题的关键。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧