【数据结构】链表面试题

203.移除链表元素
206.反转链表
876.链表的中间结点
牛客.链表中倒数第k个结点
21.合并两个有序链表
牛客.链表分隔
牛客.链表的回文结构
160.相交链表
141.环形链表
142.环形链表2

1. 移除链表元素

题目描述

在这里插入图片描述

思路：

定义一个指针cur遍历整个链表，一个tail指针，cur遍历整个链表,如果cur->val!=val,就把tail的next存放cur指针指向的地址，这样下来，可以将链表中的!=val数据连接起来，tail指针作用就是起到连接作用，注意刚开始的时候如果第一个数据！=val,首先得将head,tail移动到cur指向的头结点上，为什么13行要将head=NULL;是为了防止空链表，如果链表最后一个元素==val的话，记得循环结束，将tail->next=NULL,当free掉最后一个6时，倒数第二个元素的next还保存6的地址，当free后，6地址上存的是随机值

代码：

struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode*cur=head;
struct ListNode*tail=NULL;
head=NULL;ya
while(cur)
{ if(cur->val==val)
    {struct ListNode*del=cur;
    cur=cur->next;
     free(del);
     }
  
  else
  { if(tail==NULL)
   {tail=head=cur;}
  else
   {tail->next=cur;
   tail=tail->next; }
     cur=cur->next;}
}
if(tail)
 {tail->next=NULL;}
 return head;
}

带图调试在这里插入图片描述在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.反转链表

题目描述

在这里插入图片描述

思路1

逆序链表将存放下一个结点地址地址反过来，也就是2的next存1的地址，3的next存2的地址，4的next存3的地址，5的next存4的地址。你如果将2的next存1的地址，那么3的地址就会丢失，我们可以定义3个指针，一个指针指向前一个结点的地址，一个指针指向后一个结点指针，第三个结点n2为当前位置的指针，将n2->next存入n1,也就是在逆序链表，将每个指针都向后移动，继续修改下一个逆序方向，直到将图示中的箭头全部逆序完，n2指向空，当n3指向空后不再移动n3指针，此时n1指向的尾结点刚好是逆序之后的头结点，然后返回n1即可，如果是空链表的话，逆序之后也是空链表，直接return NULL;

代码

struct ListNode* reverseList(struct ListNode* head){
 struct ListNode*n1=NULL;
 struct ListNode*n2= head;
 if(head==NULL)
 {return NULL;}
 struct ListNode*n3=n2->next;
 while(n2)
   {n2->next=n1;
   n1=n2;
   n2=n3;
   if(n3)
     {n3=n3->next;}





}
   return n1;

}

带图调试在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路2

定义一个cur指针遍历链表，当cur指向一个结点的时候，将该结点的next保存上一个结点的地址,然后将newnode指针移动到当前cur指针指向的位置，如果这样修改的话，会丢失掉下一个结点的地址，在使用一个指针x保存cur指针指向的结点的下一个结点的地址,cur指针移动到x指针指向的地址，进行下一次循环，第一个结点逆序成为最后一个结点，他的next=NULL;

代码

struct ListNode* reverseList(struct ListNode* head){
  struct ListNode* cur=head;
  struct ListNode* newhead=NULL;
  while(cur)
    {struct ListNode*x=cur->next;
        
        
        cur->next=newhead;
    newhead=cur;
    cur=x;
    }
    return newhead;  
}

带图调试在这里插入图片描述>在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

3.链表的中间结点

题目描述

在这里插入图片描述

思路

定义一个快指针，一个慢指针，慢指针一次走一步，快指针一次走两步，结点为奇数个时，当慢指针走到一半时，快指针刚好指向尾结点，当结点数为偶数个时，当慢指针走到中间结点的第二个的时候，快指针走到尾结点的next;所以循环条件是fast和fast->next,如果有一个为NULL.循环结束。

代码

struct ListNode* middleNode(struct ListNode* head){

struct ListNode*slow=head;
struct ListNode*fast=head;
while(fast&&fast->next)
 {slow=slow->next;
 fast=fast->next->next;
 }
 return slow;
}

带图调试

奇数个结点
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

偶数个结点
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4.链表中倒数第k个结点

题目描述

在这里插入图片描述

思路

定义两个指针，都先指向头节点，先让fast指针走k步，然后每次fast指针走一步，slow指针走一步，当fast走到尾结点的下一个结点，slow指针刚好指向的是倒数第k个结点

代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
struct ListNode*fast= pListHead;
struct ListNode*slow= pListHead;
while(k)
{if(fast==NULL)//防止fast大于链表长度
    return fast;
    fast=fast->next;
k--;

}
while(fast)
{fast=fast->next;
slow=slow->next;
}
return slow;

}

带图调试，假设k等于2，
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.合并两个有序链表

题目描述

在这里插入图片描述

思路

定义一个哨兵位，定义两个指针，head和tail来先记录哨兵位的地址，然后比较list1指针指向的结点的val和list2指针指向结点的val,如果谁小，就将tail指针指向结点的next保存小的那个的地址，然后tail指针指向val小的那个结点，val小的对应的链表的指针list就指向该链表下一个结点，循环条件是list1&&list2都不为空的时候，当有一个链表被遍历完，直接把另一个链表剩下的部分的首结点地址存放在tail指针指向结点的next中，当两个链表都为空的时候，不进入循环，此时head->next=NULL,返回的就是空。

代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode*head;

struct ListNode*tail;
head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
tail->next=NULL;


while(list1&&list2)
    {if(list1->val<list2->val)
       {
        
          tail->next=list1;
           tail=tail->next;
          
          list1=list1->next;

       }
    else 
     {
     
          tail->next=list2;
           tail=tail->next;
          
          list2=list2->next;
      }
    }
      if(list1)
      {tail->next=list1;}
      if(list2)
      {tail->next=list2;}
      return head->next;
      free(head);
      
      
      
      
      }

带图调试在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.链表分隔

题目描述

在这里插入图片描述

思路

先malloc两个哨兵位，一个作为小于x链表的头，一个作为大于等于x的头，定义4个指针，分别为greathead,greattail,lesshead,lesstail.这两个 greathead,greattail 先指向大于x的哨兵位，另外两个指向小于x的哨兵位。分别将哨兵位的next置为空，如果两个都为空链表的话就不进入循环，此时的lesshead->next==NULL;返回null.定义一个cur指针遍历链表，当cur指针指向空的话，分隔结束。
循环过程中，当cur->val<x,将lesstail指针指向的结点的next保存当前cur的地址，然后lesstail指针移动到cur指针指向的地址，然后cur移动到链表的下一个结点。当cur->val>=x,将greattail指针指向的结点的next保存当前cur指针指向结点的地址,然后greattail指针移动到当前cur指针指向的结点上，然后cur移动到链表的下一个结点，当循环结束，以greathead为哨兵位的链表都是大于等于x,以lesshead为哨兵位的链表是小于x,然后将lesstail->next=greathead->next;就是将两个小于x,和大于等于x的连接起来。但是最后那里为什么要将greattail->next=NULL;
在这里插入图片描述
当链表最后一个元素小于x的话，此时的结点数据为4的结点的next还保存着结点数据为2的地址，就会成为循环链表，所以必须将greattail->next=NULL;

代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
struct ListNode* greathead;
struct ListNode* greattail;
struct ListNode* lesshead;
struct ListNode* lesstail;
greathead=greattail=(struct ListNode* )malloc(sizeof(struct ListNode ));
lesshead=lesstail=(struct ListNode* )malloc(sizeof(struct ListNode ));
greattail->next=NULL;
lesstail->next=NULL;

struct ListNode* cur=pHead;
while(cur)
   {if(cur->val<x)
       {lesstail->next=cur;
       lesstail=lesstail->next;}
    else
       {greattail->next=cur;
       greattail=greattail->next;


       }
       cur=cur->next;
}
lesstail->next=greathead->next;
greattail->next=NULL;
struct ListNode* list=lesshead->next;
free(lesshead);
free(greathead);
return list;
   // write code here
    }
};

带图调试
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

7.链表的回文结构

题目描述

在这里插入图片描述

思路

本题利用了之前求链表的中心结点和逆序链表的求解方法，先利用求链表的中心结点，用一个指针mid指向中心结点,再将mid指针指向结点以及后面的结点逆序，用rhead指针指向逆序新链表的头，然后遍历，如果head->val!=rhead->val，就直接return false,表示不相等，如果相等的话，让head指针和rhead指针指向下一个结点，等到rheadNULL,或者headNULL,循环没有在这之前return 掉，所以表示是回文结构return true。注意在这里插入图片描述
head指针走红线，rhead指针走蓝线，要么rhead先指向NULL,要么read和head同时指向NULL

代码

class PalindromeList {
  public:

    struct ListNode* reverseList(struct ListNode* head) //逆序
    {
        struct ListNode* n1 = NULL;
        struct ListNode* n2 = head;
        if (head == NULL) {
            return NULL;
        }
        struct ListNode* n3 = n2->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3) {
                n3 = n3->next;
            }





        }
        return n1;







    }
    struct ListNode* middleNode(struct ListNode* head) //找中心节点
    {

        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    bool chkPalindrome(ListNode* A)//回文结构判断
    {

     struct ListNode* mid=middleNode(A);  
     struct ListNode* rhead=reverseList(mid);
     struct ListNode* head=A;
     while(head&&rhead)
     {if(head->val!=rhead->val)
       {return false;}
      else 
      {head=head->next;
       rhead=rhead->next;
      
      }

     }
     return true;
}
};

带图调试
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

8.相交链表

题目描述

在这里插入图片描述

思路

先判断两个链表是否有交点，然后在找交点的位置，定义两个指针分别指向两个链表的头结点cur1,cur2，如果cur1->next!=NULL,如此求出链表长度，当两个循环结束时，cur1和cur2都指向各自链表的尾结点，如果有相交，则尾结点的地址是一样的，也就是cur1=cur2,然后让longlist指针指向长的链表的头，shortlist指向短的链表的头，求出两个链表的长度差，然后让指向长链表的指针longlist先走长度差步，然后让longlist,shortlist同时走，当longlist==shortlist,该位置就是相交的位置。return longlist或者shortlist,当两个链表有一个为空链表，则一定不会有相交的位置直接返回NULL,

代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{  struct ListNode *cur1=headA;
 struct ListNode *cur2=headB;
  if(headA==NULL||headB==NULL)
return NULL;

 int len1=1;
 int len2=1;
 while(cur1->next)
 {cur1=cur1->next;
     len1++;
 }
  while(cur2->next)
 {cur2=cur2->next;
      len2++;
 }
 if(cur1!=cur2)
  {return NULL;
  }
 struct ListNode* shortlist=headA;
 struct ListNode* longlist=headB;
if(len1>len2)
 { shortlist=headB;
  longlist=headA;} 
 
int gap=abs(len1-len2);
while(gap)
{longlist=longlist->next;
gap--;
}
while(shortlist!=longlist)
{longlist=longlist->next;
  shortlist=shortlist->next;
 
}
return longlist;
}

带图调试在这里插入图片描述在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

9.环形链表

题目描述

在这里插入图片描述

思路

定义一个快指针fast一次走两步，定义一个慢指针slow一次走一步，如果为奇数个结点，无环的话，fast->next=NULL;如果为偶数结点的话，并且无环，fast=NULL,表示走完了整个链表，循环结束，如果有环的话循环不会结束，，当快指针走两步的时候，慢指针走一步，他们两个会指向同一块地址，所以当slow=fast,直接return true.如果没环，循环到fast=NULL,或者fast->next=NULL;
循环结束，return false

代码

bool hasCycle(struct ListNode *head) {
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next)
{slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;

}
}
return false;


    
}

带图调试
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

10.环形链表2

题目描述

在这里插入图片描述

思路

根据上一题的思路，找出fast,slow相遇的结点，然后用新的指针meet指向这个相遇的结点，然后head指针走一步，meet指针走一步，当两个指针相遇的时候就是刚进环的结点的地址
在这里插入图片描述

代码

struct ListNode *detectCycle(struct ListNode *head) {
  struct ListNode* fast=head;
  struct ListNode* slow=head;
  while(fast&&fast->next)
     {fast=fast->next->next;
     slow=slow->next;
    if(fast==slow)
      { struct ListNode* meet=slow;
      while(meet!=head)
         {head=head->next;
          meet=meet->next;
        }
        return head;
      }
      
        }  
        return NULL;
    
    
}

带图调试
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/412881.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

大开眼界的4款黑科技软件，功能强大，网友：越用越上瘾

大开眼界的4款黑科技软件，功能强大，网友：越用越上瘾

作为一名热衷于探索软件的搞机爱好者&#xff0c;小蛙在各大软件论坛间游走&#xff0c;旨在帮助大家在纷繁复杂的Windows软件世界中&#xff0c;寻找到那些真正值得安装的神器。 在忙碌的现代生活中&#xff0c;我们的磁盘空间和时间都显得尤为宝贵&#xff0c;没必要下一些鸡…
阅读更多...
解决内嵌帆软报表出现重定向问题

解决内嵌帆软报表出现重定向问题

最近收到反馈&#xff0c;某些程序的前端通过iframe标签内嵌finebi帆软报表时&#xff0c;出现一系列问题。 问题1: 如下图所示&#xff0c;单点登录(单点登录地址schema是https)后service地址的schema协议是http, 浏览器内核的安全策略不允许http访问https。 解决方案&#xf…
阅读更多...
java数据结构与算法刷题-----LeetCode530. 二叉搜索树的最小绝对差

java数据结构与算法刷题-----LeetCode530. 二叉搜索树的最小绝对差

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 解题思路&#xff1a;时间复杂度O(n)&#xff0c;空间复杂度O(n) 一个有序…
阅读更多...
阻抗与电气模型（三）

阻抗与电气模型（三）

阻抗的定义为电压与电流的比值&#xff0c;通常用大写字母Z表示。Z V/I&#xff0c;当信号沿互连传播时&#xff0c;将不断的探测互连的阻抗&#xff0c;并做出相应的反应。阻抗又称为交流&#xff08;AC&#xff09;电阻。 如果知道了互连的阻抗和传播时延&#xff0c;也就知…
阅读更多...
如何改变.net托管的入口main函数

如何改变.net托管的入口main函数

有小伙伴问: .NET托管入口Main函数可以修改成别的函数&#xff0c;用来作为程序的入口吗&#xff1f; 答案&#xff1a;当然是可以的。这也算是.NET里面非常简单的骚操了。本篇来用最新的.NET8演示下&#xff0c;如何修改Main入口。 1.简单控制台例子&#xff1a; namespace…
阅读更多...
金融行业数字化人事管理：组织管理、风险管控、职级晋升一体化

金融行业数字化人事管理：组织管理、风险管控、职级晋升一体化

目前&#xff0c;金融行业正在全面推进数字化转型&#xff0c;推动行业高质量发展。人力资源是组织发展的核心竞争力&#xff0c;数字化的人事管理能够为金融组织降本增效。 行业痛点 1、金融行业分支机构多、人员规模大&#xff0c;随着组织的快速发展&#xff0c;集团内组织…
阅读更多...
Postman Tests：简介与示例

Postman Tests：简介与示例

Postman 不仅是一个强大的 API 开发工具&#xff0c;它还提供了创建自动化测试脚本的能力&#xff0c;这些脚本可以用于检验API请求得到的响应是否符合预期。这些测试脚本被称为 “Tests”&#xff0c;支持使用 JavaScript 编程语言进行编写&#xff0c;并且 Postman 提供了一系…
阅读更多...
图片录入设备、方式与质量对图片转Excel的影响

图片录入设备、方式与质量对图片转Excel的影响

随着数字化时代的到来&#xff0c;图片已经成为人们日常生活中不可或缺的一部分。在各行各业中&#xff0c;图片的应用越发广泛&#xff0c;从而促使了图片处理技术的快速发展。然而&#xff0c;图片的质量对于后续数据处理和分析的准确性和可靠性有着至关重要的影响。本文将从…
阅读更多...
IDEA 创建Spring Boot 项目整合jdbc详细步骤

IDEA 创建Spring Boot 项目整合jdbc详细步骤

IDEA 创建Spring Boot 项目&整合jdbc详细步骤 1、打开 IntelliJ IDEA 软件2、使用 "Spring Initializr" 作为项目类型&#xff0c;新建项目工程3、选择对应的SpringBoot版本和依赖4、Spring Boot 项目的结构5、创建一个TestController&#xff0c;并运行6、整合j…
阅读更多...
用Python实现创建餐厅评分数据分析表

用Python实现创建餐厅评分数据分析表

代码的功能是创建一个雷达图&#xff08;Radar Chart&#xff09;&#xff0c;也称为蜘蛛网图&#xff08;Spider Chart&#xff09;&#xff0c;用来展示不同餐厅在多个维度上的评分。雷达图是一种非常适合展示多维数据的图形&#xff0c;它能够清楚地显示每个数据点在多个变量…
阅读更多...
发现了一个老师都该知道的成绩发布神器！

发现了一个老师都该知道的成绩发布神器！

老师们&#xff0c;你们是不是还在为每次考试后的成绩发布而烦恼&#xff1f;手动整理、逐个通知&#xff0c;简直让人头疼不已&#xff01; 想象一下&#xff0c;你只需将成绩整理成Excel表格&#xff0c;一键上传&#xff0c;立马就能生成一个专属的成绩查询小程序。是不是感…
阅读更多...
《数据治理简易速速上手小册》第6章 数据访问与共享（2024 最新版）

《数据治理简易速速上手小册》第6章 数据访问与共享（2024 最新版）

文章目录 6.1 管理数据访问权限6.1.1 基础知识6.1.2 重点案例&#xff1a;金融公司的 RBAC 系统6.1.3 拓展案例 1&#xff1a;医疗保健机构的 ABAC 实现6.1.4 拓展案例 2&#xff1a;科技公司的最小权限策略 6.2 数据共享的策略和工具6.2.1 基础知识6.2.2 重点案例&#xff1a;…
阅读更多...
Python海龟绘图：绘出最靓丽的景色

Python海龟绘图：绘出最靓丽的景色

目录 一、引言 二、海龟绘图库的基本使用 三、绘制靓丽的景色 案例一&#xff1a;绘制日出或日落 案例二&#xff1a;绘制森林 四、总结与建议 五、展望未来 六、附录 一、引言 在Python编程中&#xff0c;除了强大的数据处理和逻辑运算能力&#xff0c;还有一项非常有…
阅读更多...
NXP实战笔记（十一）：32K3xx基于RTD-SDK在S32DS上配置DFLASH、MemAcc、Fee

NXP实战笔记（十一）：32K3xx基于RTD-SDK在S32DS上配置DFLASH、MemAcc、Fee

目录 1、概述 2、RTD-SDK配置之Cache_Ip 3、RTD-SDK配置之Mem_43_InFls 4、RTD-SDK配置之MemAcc 5、RTD-SDK配置之Fee 6、代码示例 1、概述 S32K3目前安装的RTD普遍使用的是R22-11版本的AUTOSAR规范&#xff0c;作为一直使用AUTOSAR4.2.2的程序员来讲&#xff0c;属实迭代…
阅读更多...
Connection模块类功能联调(整合三)

Connection模块类功能联调(整合三)

目录 概要 tcp_cli.cc tcp_srv.cc server.hpp 测试结果 第三次整合 概要 本主要是将以下模块进行整合测试 Connection管理类实现(模块六)-CSDN博客 EventLoop整合与TimerWheel联合调试(整合二)-CSDN博客 tcp_cli.cc #include "../source/server.hpp"int main…
阅读更多...
在编教师要跨市调可以吗

在编教师要跨市调可以吗

经常看到有人问&#xff1a;“在编教师能否跨市调动&#xff1f;”这个问题看似简单&#xff0c;实则背后涉及了多重因素。今天&#xff0c;就让我来为大家揭秘在编教师跨市调动的可能性及其背后的那些关键因素。 教师作为事业单位的在编人员&#xff0c;其调动并不是一件随心所…
阅读更多...
个人玩航拍，如何申请无人机空域？

个人玩航拍，如何申请无人机空域？

我们在《年会不能停》一文中&#xff0c;有分享我们在西岭雪山用无人机拍摄的照片和视频&#xff0c;有兴趣可以去回顾。 春节的时候&#xff0c;趁着回老家一趟&#xff0c;又将无人机带了回去&#xff0c;计划拍一下老家的风景。 原本以为穷乡僻壤的地方可以随便飞&#xf…
阅读更多...
手机厂商们，画了一张「AI大饼」

手机厂商们，画了一张「AI大饼」

【潮汐商业评论/原创】 “未来世界&#xff0c;大部分人类可能是多余的。” 这是尤瓦尔赫拉利在《未来简史》中被大众最为争议的观点。如今&#xff0c;当AI正从二维空间“概念”走向多维世界“应用”时&#xff0c;人类社会的生产力重心也将随之向人工智能转移&#xff0c;人们…
阅读更多...
配置用户通过IPv6方式上网

配置用户通过IPv6方式上网

组网需求 运营商为企业分配了WAN侧的IPv6地址1111:2222:A0EE:6::2/64和LAN侧的IPv6地址1111:3333:E840:2::1/64&#xff0c;企业通过运营商提供的IPv6地址配置上网。 图1 配置用户通过IPv6方式上网 操作步骤 1、在IPS上的配置 interface GigabitEthernet0/0/4 ipv6 enable…
阅读更多...
绿幕背景抠图SDK解决方案

绿幕背景抠图SDK解决方案

随着影像技术的日益发展和普及&#xff0c;视频制作和图像处理已经成为众多行业不可或缺的一环。美摄科技&#xff0c;作为业内领先的影像技术提供商&#xff0c;针对企业需求&#xff0c;推出了全新的绿幕背景抠图SDK解决方案&#xff0c;旨在为企业提供更加高效、精准的影像处…
阅读更多...
最新文章

Copyright @ 2022~2023