链表经典面试题【典中典】

简介: 双指针–将指针指向前面,最后一个变成头。两个指针,一前一后

💯💯💯链表经典面试题❗❗❗炒鸡经典,本篇带有图文解析,建议动手刷几遍。


🟥1.反转链表


7443c8a108a24a0ab5c741fd2ddf20c1.png


方法一:利用双指针逆转方向


将各个结点的连接方向都倒过来,2结点指向1结点,3结点指向2结点等,我们只要将让每个结点的next指向前一个结点的地址


双指针–将指针指向前面,最后一个变成头。两个指针,一前一后

注意点:


  • 单链表不能往前走
  • 第一个指针首先指向NULL ,第二个指针在后面,这两个指针用来转变指向

不过这时第二个指针的后面的地址无法知道,这时需要第三个指针用来记录第二个指针后面的结点的地址。

  • 当第三个指针往后走的时候可能为NULL,要注意下

3b3f0b355c6f443695b61eeccc3ad12e.png


代码如下:


struct ListNode* reverseList(struct ListNode* head)
{
   if(head==NULL)//如果链表为空则直接返回NULL
    return NULL;
   struct ListNode* prev = NULL;//与cur搭配,记录前面的,一开始为NULL
    struct ListNode* cur = head;//一开始为第一个结点,所以将head传给cur,让cur遍历链表
    struct ListNode* next =cur->next;//next用来记录cur后面结点的地址
    while (cur)//当cur不为NULL时进行
    {
        //方向逆转
        cur->next = prev;//将每一个结点的next指向前一个结点的地址
        //迭代--让我们的条件往后执行
        prev = cur;//让pre跑到cur的位置上来
        cur = next;//让cur跑到next的位置上来
        if (next)//这里next可能会跑着跑着为NULL了,所以需要判断下
            next = next->next;//往后跑
    }
    return prev;//最后尾就是头了,将尾传回去
}


方法2:利用头插原理


取原结点头插到新链表


原本是1 2 3 4 5


我们只要将每个结点拿下来,然后头插到一个新链表上就会变成5 4 3 2 1了


5789518a0d394482845eba76a23d8d7f.png


代码如下:


struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;//利用cur进行遍历,不要用形参head
  struct ListNode* newnode = NULL;//首先创建一个新的空链表
  while (cur)//当cur为空时结束
  {
    //首先要记录下来cur后面结点的地址
    struct ListNode* next = cur->next;
    //头插
    cur->next = newnode;//将取下来的结点头插到新链表中
    newnode = cur;//更新头指针
    cur = next;//cur要往后走
  }
  return newnode;//返回新链表的头指针
}


🟧2.合并两个有序链表


1fa36acdb2ed4d0bbe74503e6b3894d6.png


这种题目在数组中也有类似的,原理也是一样,合并两个有序数组

也就是依次比较取小的结点尾插,最后如果比较完还有结点直接尾插到没有结点的后面去。


注意点:


  • 当第一次尾插到一个新链表时,我们需要的 是进行直接赋值,将第一个结点直接赋值给新链表的头指针而不能进行尾插

  • 当第一次以后才可以进行真正的尾插

  • 当其中有一个或两个链表为空链表的话,那么直接跳过比较环节,而进入将还有结点的直接尾插到没有结点的后面去

这时因为没有结点的链表为NULL,所以就无法访问它的next也就无法将它和另一个链表链接起来。

所以这时我们需要在前面讨论一下,当其中有一个链表为NULL,则直接返回另外一个链表。

方法1:


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  if (list1 == NULL)//当链表1为空则直接返回链表2
    return list2;
  if (list2 == NULL)//当链表2为空则直接返回链表1
    return list1;
  struct ListNode* cur1 = list1, * cur2 = list2;//利用cur1,cur2遍历链表
  struct ListNode* head = NULL, * tail = NULL;//head,用来传回,tail用来找尾
  while (cur1 && cur2)//当其中有一个结束就结束
  {
    if (cur1->val < cur2->val)//哪个小就尾插谁
    {
      //将小的尾插
      //但一开始为空第一步就是赋值
      if (head == NULL)
      {
        head = tail = cur1;
      }
      //接下来才是真正的尾插
      else
            {
                tail->next = cur1;//将cur1链接在tail的后面
          tail = tail->next;//tail要往后找尾,这样就不需要每次从开始进行找尾了
            }
      cur1 = cur1->next;//cur往后走
    }
    else 
    {
      //将小的尾插
      //但一开始为空第一步就是赋值
      if (head == NULL)
      {
        head = tail = cur2;
      }
      //接下来才是真正的尾插
      else
            {
                tail->next = cur2;
          tail = tail->next;
            }
      cur2 = cur2->next;
    }
  }
  //将长的链表指针尾插到tail后面
  //不过还有一种情况就是plist为空cur1为空,则tail还是NULL,这种情况需要讨论
  if (cur1)
  {
    tail->next = cur1;
  }
  else
  {
    tail->next = cur2;
  }
  return head;//返回head
}

bbb5d008e80b454382dbc2335d7282b5.png

e689c7610a1444279b780ec12111ec62.png


还有一种方法可以避免讨论tail的next是否为空,和第一次尾插需要赋值等问题。


我们可以利用带有头哨兵卫的头结点。


这样tail永远不可能为空了,就不需要讨论那么多为空的情况了。


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* cur1 = list1, * cur2 = list2;
  struct ListNode* head =NULL,* tail = NULL;
  struct ListNode* guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//动态开辟一个哨兵头结点,让tail一开始就指向头结点,这样tail就永远不会为NULL了
  while (cur1 && cur2)//当其中有i一个结束就结束
  {
    if (cur1->val < cur2->val)
    {
      //将小的尾插
      //不需要进行讨论第一个头节点为NULL的情况了,直接进行尾插
        tail->next = cur1;
        tail = tail->next;
      cur1 = cur1->next;
    }
    else
    {
      //将小的尾插
        tail->next = cur2;
        tail = tail->next;
          cur2 = cur2->next;
    }
  }
  //将长的链表指针尾插到tail后面
  //如果没有哨兵头,plist为空cur1为空,则tail还是NULL,这种情况就需要讨论
  //但先走有了哨兵头结点,tail不可能为空,直接让tail的next与另一个链表剩余的结点链接起来
  if (cur1)
  {
    tail->next = cur1;
  }
  else
  {
    tail->next = cur2;
  }
    head=guard->next;//将第一个结点的地址记录下来
    free(guard);//释放guard
  return head;
}

4c7a95496d9b48fc82c61e6d632c029b.png


🟨3.链表分割


3295d952649e4d31b303c5602b537f7e.png


要求将所有小于x的结点排在其他结点之前,且不能改变原来的数据顺序

我们可以这样做:


  1. 将小于x的结点插入到一个链表中
  2. 将大于x的结点插入到一个链表中
  3. 最后将两个链表链接起来。

1fde6ceda248402e9ee53a650a865bfa.png


不过这里我们最好使用带有哨兵头的链表,这样可以减少进行对NULL的讨论不然会很麻烦


比如如果数据全是 6 6 6 6 6 而x为5


则less链表为空,那么将两个链表链接起来有会出问题,ltail都为NULL还有next吗?,所以我们使用带有哨兵卫的链表能很好的减少这种讨论。


aa725aff1493433fb9600d17f686ba98.png

f6bf2b2f3ffb4a258771072584e7dcf7.png

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* Lguard,*Gguard,*ltail,*gtail;
        Lguard=ltail=(ListNode*)malloc(sizeof(ListNode));//less链表的哨兵头
        Gguard=gtail=(ListNode*)malloc(sizeof(ListNode));//greater链表的哨兵头
        ltail->next=NULL;//一开始要置NULL
        gtail->next=NULL;
        ListNode* cur=pHead;//利用cur进行遍历
        while(cur)
        {
            if(cur->val<x)//如果小于x就尾插到less的链表中
            {
                ltail->next=cur;//将小的数据尾插到ltail的后面
                ltail=ltail->next;//找尾
            }
            else {
            gtail->next=cur;//将大的数据尾插到gtail后面
            gtail=gtail->next;
            }
            cur=cur->next;//每次cur也要往后走
        }
        ltail->next=Gguard->next;//让两个链表链接起来
        gtail->next=NULL;//想一想这一步是为什么呢?因为最后7的next还链接着2呀,这样就造成回环了。
        所以需要将gtail的next置为NULL
        pHead=Lguard->next;//第一个结点
        free(Lguard);//释放
        free(Gguard);//释放
        return pHead;//返回第一个结点地址
    }
};

3c6dbb95b291455b9dcec357493c3a59.png


🟩4.链表的回文结构


99030c4d43814d7f96ef8c615626ab1a.png


我们看到链表时有时就会想转空子,想先使用数组来存储链表的数据,然后再进行判断,我们在知道链表长度的前提下理论上是可以的,但最好不要这样做,如果不知道长度,我们还需要动态增容等,所以要抛弃这个想法。


那怎么判断回文结构呢?


回文结构也就是对称,从中间对称,左边与右边对称,如果我们把右边逆转下,那么右边就和左边一样了。所以我们就可以根据左边和右边是否一样进行判断了


  1. 首先我们需要找到中间结点
  2. 逆转中间结点以后的结点
  3. 从逆转开始的位置与开头进行比较


逆转链表,查找链表的中间结点我都已经写过了,这里直接就复制过来。

《找链表的中间结点》

《反转链表》


1a342a0cfd9342948b1330f660e15c39.png


class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head)//找链表中间结点
{
   struct ListNode *fast,*slow;
   fast=slow=head;
   while(fast!=NULL&&fast->next!=NULL)
   {
       slow=slow->next;
       fast=fast->next->next;
   }
   return slow;
}
struct ListNode* reverseList(struct ListNode* head)//反转链表
{
struct ListNode* cur = head;
  struct ListNode* newnode = NULL;
  while (cur)
  {
    //首先要记录下来cur后面结点的地址
    struct ListNode* next = cur->next;
    //头插
    cur->next = newnode;
    newnode = cur;//更新头指针
    cur = next;//cur要往后走
  }
  return newnode;
}
    bool chkPalindrome(ListNode* phead)
     {
      ListNode *mid=  middleNode(phead);//找中间结点
      ListNode *rhead = reverseList(mid);//逆转中间结点以后
      //比较链表前面数据与逆转后的数据
      while(rhead)//当逆转后的结点走到NULL时结束
      {
        if(rhead->val!=phead->val)
           return false;//当有一个不等于就然后false
          phead=phead->next;
          rhead=rhead->next;
      }
      return true;//走到这说明都相等
    }
};

32ebc83455044aada0df23abd2225dac.png


🟦5.相交链表


eebbc6376fc44ec092e7c04608211dac.png


怎么判断两个链表是否相交呢?

怎么返回这个相交结点呢?


传统思想可能会让链表A中每个结点的地址与链表B中结点的地址都比较一下,当第一次比较相同时,就是相交结点,不过这种方法的时间复杂度为O(N^2)了,不好,有没有让时间复杂度为O(N)的呢?


好的让我来告诉你吧:

如果两个链表是相交的,那么它们的尾结点的地址一定相同,如果尾结点地址不相同那么肯定不相交。

接着让长的链表先走长度差步,然后两个链表再一起走,当两个链表结点地址比较相同时就是相同结点的位置。


所以


  1. 求出两个链表的长度,判断是否相交。
  2. 让长度长的链表先走长度差步,然后一起走
  3. 两个链表结点地址相比,第一次相同的为相交结点


0dce476cf50546b693a57cbb3c9218ce.png


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
      struct ListNode *cur1=headA,*cur2=headB;//用cur1遍历链表A,用cur2遍历链表2
    int lena=0;
    int lenb=0;
    while(cur1->next)//记录链表A的长度
    {
        cur1=cur1->next;
        ++lena;
    }
    while(cur2->next)//记录链表B的长度
    {
        cur2=cur2->next;
        ++lenb;
    }
    if(cur1!=cur2)//如果链表尾结点不相同那么肯定不相交
    return NULL;
    int gap=abs(lena-lenb);//长度差,但我们不知道哪个链表长
    struct ListNode *longlist=headA,*shortlist=headB;
    if(lenb>lena)//所以我们需要讨论下
    {
     longlist=headB,shortlist=headA;
    }
    while(gap--)//让长的链表先走长度差步
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)//然后两个链表一起走,当没有结点地址相同时则一起走
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;//最后如果有相同的就返回
}
相关文章
|
6天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
24天前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
24天前
|
存储 算法 索引
链表面试题
链表面试题
链表面试题
|
24天前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
24天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
24天前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
24天前
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
|
26天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
24 0
|
26天前
|
算法 程序员 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
25 0
|
26天前
|
算法 C语言 C++
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
16 0