前言
此次练习题有两道!
有点小难度,但相信难不住大家的!
我也会给出两道OJ题的链接,大家也赶快去试一试吧
一、返回链表开始入环的第一个节点
题目链接:OJ链接
提示:
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
本题有两个解析思路~
思路一
代码演示:
//解题方法一
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *move1=head;
struct ListNode *move2=head;
while(move1&&move2&&move2->next){//快慢指针移动
move1=move1->next;
move2=move2->next->next;
if(move1==move2){{//找到相遇点
struct ListNode *meet=move1;//meet从相遇点开始移动
struct ListNode *move3=head;//move3从head开始移动
while(meet!=move3){//两个指针同时移动找到起始点
meet=meet->next;
move3=move3->next;
}
return meet;
}
}
return NULL;
}
思路二
提示:如果不了解如何找出公共点的的话,前面的博客会对大家有所帮助!
博客链接:单链表OJ题
代码演示:
//解题方法二
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *move1=head;
struct ListNode *move2=head;
while(move1&&move2&&move2->next){//快慢指针移动
move1=move1->next;
move2=move2->next->next;
if(move1==move2){//找到相遇点
struct ListNode *temp=move1;//保存相遇点位置
move1=move1->next;//将move1变为第二链表起始点
temp->next=NULL;//将相遇点的next置空
struct ListNode *head1=head;
struct ListNode *head2=move1;
int len1=0,len2=0;
while(head1!=NULL){//计算链表长度
len1++;
head1=head1->next;
}
while(head2!=NULL){
head2=head2->next;
len2++;
}
int k=abs(len1-len2);//得到两链表长度相减的绝对值
//将longs指向较长的链表,shorts指向较短的链表
struct ListNode *shorts=head;
struct ListNode *longs=move1;
if(len1>len2){
shorts=move1;
longs=head;
}
while(k--&&longs!=NULL){//较长的链表移动k位
longs=longs->next;
}
if(k>0&&longs==NULL){
return NULL;
}
while(shorts!=longs){//两链表同时遍历,找到第一个公共点
shorts=shorts->next;
longs=longs->next;
}
return longs;
}
}
return NULL;
}
二、返回链表的深度拷贝
题目链接:OJ链接
提示:
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。
解题思路:
代码演示文章来源:https://www.toymoban.com/news/detail-632151.html
struct Node* BuyNewnode(int x){//创建结点函数
struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));
newnode->val=x;
newnode->next=NULL;
newnode->random=NULL;
return newnode;
}
//查找random所在位置的函数
struct Node* findrandom(struct Node* head,struct Node* newhead,struct Node* random){
struct Node*move1=head;
struct Node*move2=newhead;
while(move1!=random){
move1=move1->next;
move2=move2->next;
}
return move2;
}
struct Node* copyRandomList(struct Node* head) {
struct Node*move=head;
struct Node*newhead=NULL;
struct Node*tail=NULL;
while(move!=NULL){//将新建结点依次尾插到新链表中
if(tail==NULL){
struct Node*newnode= BuyNewnode(move->val);
newhead=tail=newnode;
move=move->next;
}
else{
struct Node*newnode= BuyNewnode(move->val);
tail->next=newnode;
tail=tail->next;
move=move->next;
}
}
struct Node*setran=newhead;
struct Node*findran=head;
while(setran&&findran){
struct Node*temp=findrandom(head,newhead,findran->random);
setran->random=temp;
setran=setran->next;
findran=findran->next;
}
return newhead;
}
总结
这次的题目稍稍有些难度!
但是绝对难不倒大家的!
加油! 加油!文章来源地址https://www.toymoban.com/news/detail-632151.html
到了这里,关于数据结构——单链表OJ题(第二弹)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!