当前位置：首页 > news >正文

链表相关题目

news 2026/5/12 13:04:31

链表相关题目

文章目录

链表相关题目
- 一、前言
- 二、链表
- - 2.1 本质
  - 2.2 误区
  - 2.3 思路
  - 2.4 题型
  - - 2.4.1 leetcode
    - 2.4.2 洛谷
  - 2.5 补充
  - - 2.5.1 静态链表
    - 2.5.2 跳表
- 三、小结

一、前言

接下来就要进入基础数据结构部分了~

二、链表

2.1 本质

链表就是把数据离散开

2.2 误区

头结点：不存任何数据
首元结点：存放着第一个数据

2.3 思路

根据题意选择合适的链表类型，如：单链表：带不带头节点
模拟遍历/快慢指针思想

2.4 题型

2.4.1 leetcode

206.反转链表（头插法）

两种思路：

头插法：p = q; q = p->next; p->next = NULL;从第一个节点开始，挨个摘下每一个节点，摘下后用头插法建立新的链表

双指针：

t指针：防止后面的部分丢失
p指针：遍历链表
q指针：为了使p指向前面的节点，q指向前面的节点
q=NULL;p=head;t=p->next;p->next=q;p=q;p=t;

代码

// 反转链表——在原链表进行操作(无malloc)#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;typedefstructListNode// 定义链表节点{intval;ListNode*next;}ListNode;ListNode*reverseList(ListNode*head){ListNode*p=l;ListNode*q=NULL;while(p!=NULL){ListNode*t=p->next;// 防止后面的丢失p->next=q;// 往前指q=p;// 顺序不能反p=t;}returnq;}intmain(){intn,x;cin>>n;ListNode*l=head;ListNode*r=NULL;for(inti=1;i<=n;i++){cin>>x;ListNode*s=(ListNode*)malloc(sizeof(ListNode));s->val=x;s->next=NULL;if(i==1){l=s;r=s;}else{// 尾插法r->next=s;r=s;}}l=reverseList(l);ListNode*s=l;while(s!=NULL){cout<<s->val<<" ";s=s->next;}return0;}

LCR 140.训练计划 II

题意：给一个链表，找倒数第cnt个数据

思路：快慢指针

代码

ListNode*f=head;ListNode*s=head;while(f->next!=NULL){// f先走，s和f相距cnt个if(cnt>1){f=f->next;cnt--;continue;}// s和f一起走s=s->next;f=f->next;}// 最后s指向的的就是第cnt个returns;

142.环形链表 II
题意：判断有没有环以及从哪个节点开始进入环的（类似于跑步套圈的情况）
思路
如果有环，总有一天快指针会和慢指针相遇，并且快慢指针永远不会跑到空的地方
如果没环，快指针会很快指向空的地方
如何看从哪里开始进入环呢？
快慢指针：快慢指针相遇一定是在圈里相遇。假设相遇点是x，f指针走的快，先绕圈；s指针走的慢，后开始绕圈。f指针走了a + b，继续走；s指针先走了a，进入圈刚走了b就和f指针相遇了。此时，f已经跑了n圈，a + n * (b + c) + b。如图：
快指针和慢指针走，当它们两个相遇的时候，快指针就停下来，在用一个慢指针从起点开始走，慢指针继续走，当第一个慢指针又和第二个慢指针相遇的时候，就是开始进入圈的点
代码
```
// 判断成环#include<iostream>#include<algorithm>usingnamespacestd;typedefstructListNode{intval;ListNode*next;}ListNode;ListNode*detectCycle(ListNode*head){ListNode*f=head;ListNode*s=head;while(f!=NULL){s=s->next;if(f->next==NULL){returnNULL;}f=f->next->next;if(s==f){ListNode*p=head;while(p!=s){p=p->next;s=s->next;}returnp;}}returnNULL;}intmain(){intn,x;// 建立单链表cin>>n;ListNode*l=head;ListNode*r=NULL;for(inti=1;i<=n;i++){cin>>x;ListNode*s=(ListNode*)malloc(sizeof(ListNode));s->val=x;s->next=NULL;if(i==1){l=s;r=s;}else{// 尾插法r->next=s;r=s;}}cin>>x;ListNode*ans=detectCycle(l);if(ans==NULL){cout<<"无环"<<endl;}else{cout<<ans->val<<endl;}return0;}
```