【数据结构】链表面试题

这篇具有很好参考价值的文章主要介绍了【数据结构】链表面试题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

带图调试
【数据结构】链表面试题,数据结构,数据结构
【数据结构】链表面试题,数据结构,数据结构
【数据结构】链表面试题,数据结构,数据结构文章来源地址https://www.toymoban.com/news/detail-713782.html

到了这里,关于【数据结构】链表面试题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构练习】链表面试题锦集一

    目录 前言: 1. 删除链表中所有值为key的节点  方法一:正常删除,头结点另外讨论  方法二:虚拟头结点法  方法三:递归 2.反转链表  方法一:双指针迭代   方法二:递归法 3.链表的中间结点   方法:快慢指针法 4. 链表中倒数第k个结点  方法:快慢指针方法 5.合并两个

    2024年02月11日
    浏览(36)
  • 数据结构常见面试题及详细java示例

    下面是一些常见的数据结构面试题以及使用Java实现的解决方案。 1、如何在给定数组中找到重复的元素?         使用HashSet是一个常见的解决方法。 2、链表反转         反转链表是最常见的数据结构问题之一。以下是用Java实现的一个例子。 3、二叉树的深度     

    2024年04月12日
    浏览(37)
  • 单链表面试题思路分享二

    我们紧接上文单链表面试题分享一来看看本章我要分享的题目,共四个题目,我还是把它在力扣或者牛客网的链接交给大家: 1.合并两个有序链表 力扣21题----- 2.链表的分割 牛客网cc149----- 3.链表的回文结构 力扣234题----- 4.链表相交 力扣160题, 本次分享还是和之前一样,代码用c语言

    2023年04月23日
    浏览(50)
  • 【链表面试题】解决环形链表和相交链表问题

    在力扣上发现这样的几道题,尝试做了一下,也发现了一个关于这类题的一种做法:快慢指针的使用。废话不多说,上例题 目录 一、环形链表 1.定义(概念) 2.如何判断是否为环形链表 1.快慢指针 2.为什么快指针一次走两个结点 3.例题分析 二、相交链表 1.例题分析 2.解法分

    2023年04月17日
    浏览(43)
  • Tecplot数据结构——结构数据(结构网格)与非结构数据(非结构网格)

    结构数据可以是一维、二维或三维的,下面以二维的数据格式为例。 在记事本中写入以下字符,并将文件以.plt或.dat为后缀命名。 其中数据总数为I*J=20,结构数据顺序为point格式,顺序为:(I,J)=(1,1), (I,J)=(2,1), … (I,J)=(Imax,1), (I,J)=(1,2), (I,J)=(2,2), (I,J)=(Imax,2), … (I,J)=(Imax,Jmax).

    2024年02月15日
    浏览(54)
  • 数据结构与算法——数据结构有哪些,常用数据结构详解

    数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?下面将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构

    2024年02月15日
    浏览(60)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(49)
  • 结构化数据、非结构化数据、半结构化数据

    结构化的数据一般是指可以使用关系型数据库表示和存储,可以用二维表来逻辑表达实现的数据。例如:需要多少个属性,每个属性什么类型,每个属性的取值范围等等,类似下图所示, 提前定义好了一个二维矩阵的元数据 ,包含有列名称、列的类型、列的约束等:   可见

    2024年02月09日
    浏览(62)
  • 【数据结构】何为数据结构。

    🚩 WRITE IN FRONT 🚩    🔎 介绍:\\\"謓泽\\\"正在路上朝着\\\"攻城狮\\\"方向\\\"前进四\\\" 🔎 🏅 荣誉:2021|2022年度博客之星物联网与嵌入式开发TOP5|TOP4、2021|2022博客之星TOP100|TOP63、阿里云专家博主、掘金优秀创作者、全网粉丝量6w+、全网访问量100w+ 🏅 🆔 文章内容由 謓泽 原创 如需相关

    2024年02月08日
    浏览(60)
  • 【数据结构】什么是数据结构?

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 目录 🎏数据结构的定义 🎏结语 数据结构(Data Structure)是计算机 存储 , 组织数据的方式 ,指 相互之间存在一种或多种特定关系的数据元素的集合 . 这么讲可能有些抽象,放一张图大家可能好理解一

    2024年02月07日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包