链表相关题目

链表相关题目

一、前言

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

二、链表

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

2.4.2 洛谷

• P1996 约瑟夫问题

2.5 补充

2.5.1 静态链表

用数组描述的链表（结构体数组）

2.5.2 跳表

在有序链表的基础上增加了“跳跃”的功能，对有序的链表实现二分查找功能
多层链表，每一层都有序，最下面的链表是最原始的链表（包括所有数据），从下往上节点折半提取元素上移。

三、小结

本篇结合灵神题单、洛谷官方书籍等以及我的一些想法等