66链表三连击：面试官最爱考的三个单链表问题，你真的会吗？

一.引言

       在算法面试中，链表问题因其独特的指针操作和边界条件处理，常常成为考察面试者编程功底的“重灾区”。单链表作为最基础的数据结构之一，其相关问题更是层出不穷。本文精选了三道高频面试题，旨在帮助大家深入理解链表的特性，掌握其常见操作技巧，并提供多种解题思路。通过这三道题的练习，相信你对链表的理解会更上一层楼，在面试中也能从容应对。

二.移除链表元素

题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

方法一：直接修改原链表

这种方法通过两个指针 cur 和 prev 来遍历链表。cur 指向当前正在检查的节点，prev 指向 cur 的前一个节点。

• 当 cur 指向的节点值等于 val 时，我们需要删除它。

  • 如果 cur 是头节点（即 prev 为 NULL），我们直接将 head 指向 cur 的下一个节点。

  • 如果 cur 不是头节点，我们将 prev 的 next 指针直接指向 cur 的下一个节点，跳过 cur。

  • 无论哪种情况，都必须释放 cur 指向的内存，并将 cur 更新为它的下一个节点。

• 如果 cur 的节点值不等于 val，则 cur 和 prev 同时向后移动一位，继续遍历。

  struct ListNode* removeElements(struct ListNode* head, int val)
  {
      if(head == NULL)
      {
          return NULL;
      }
      struct ListNode* cur = head;
      struct ListNode* prev = NULL;
      while(cur)
      {
          //如果当前节点是需要删除的节点
          if(cur->val == val) 
          {
              //首先保存下一个节点
              struct ListNode* next = cur->next;
              //如果删除的为头节点，更新头节点
              //否则让当前节点的前趋节点链接next节点
              if(prev == NULL)
              {
                  head = cur->next;
              }
              else
              {
                  prev->next = cur->next;  
              }
              //释放当前节点，让cur指向next
              free(cur);
              cur = next;
          }
          else
          {
              //如果cur不是需要删除的节点，则更新prev,cur
              prev = cur;
              cur = cur->next;
          }
      }
      return head;
  }

方法二：尾插法

另一种更优雅的思路是创建一个新的链表，只保留原链表中值不等于 val 的节点。

• 我们创建两个指针 newHead 和 newTail 来管理新链表。

• 遍历原链表，对于每一个节点 pcur：

  • 如果 pcur->val 不等于 val，我们就将它通过尾插的方式插入到新链表中。

  • 如果 pcur->val 等于 val，我们直接跳过它，不进行任何操作。

• 遍历结束后，将新链表的尾节点的 next 指向 NULL，确保链表结束。

• 最后返回新链表的头节点 newHead。

这种方法的优点是思路清晰，代码逻辑更简单！！！

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
    ListNode* newHead, *newTail;
    newHead = newTail = NULL;
    ListNode* pcur = head;
    while(pcur)
    {
        //满足条件尾插
        if(pcur->val != val)
        {
            //执行尾插操作
            if(newHead == NULL)
            {
                newHead = newTail = pcur;
            } 
            else
            {
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newTail)
    {
        newTail->next = NULL;    
    }
    return newHead;
}

特别值得注意的是：程序的最后，需要判断一下尾节点newTail是否为空。如果函数传参进来的头节点head本身就是空，那此时尾节点newTail也是空，此时解引用必然出错，这种情况对应上文示例二。

三.反转链表

题目描述：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

方法一：三指针遍历法

这种方法使用三个指针来完成链表的反转：

• n1：指向已经反转部分的尾部，也就是当前节点的前一个节点。

• n2：指向当前正在处理的节点。

• n3：指向 n2 的下一个节点，用于在改变 n2 的 next 指针后，还能继续访问到链表的后续部分。

遍历过程中，我们依次将 n2 的 next 指针指向 n1，然后将三个指针都向后移动一位，直到 n2 为空，此时 n1 就是新的头节点。

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

方法二：头插法构建新链表

这种方法更加直观，我们遍历原链表，并将每个节点逐一“头插”到一个新的链表中。

• 创建一个空的头节点 newhead。

• 遍历原链表，用 cur 指针指向当前节点。

• 在每次循环中，先用一个临时指针 next 保存 cur 的下一个节点。

• 然后将 cur 插入到 newhead 的头部：cur->next = newhead，并更新 newhead 为 cur。

• 最后将 cur 移动到 next，继续下一次循环。

当遍历结束时，newhead 就是反转后的链表的头节点。

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插新节点，更新头
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

四.链表的中间节点

题目描述：给你单链表的头结点 head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

解题思路：这道题最巧妙的解法是利用快慢指针。我们设置两个指针，一个快指针 fast，一个慢指针 slow，它们都从链表的头节点开始。

• 在每一次循环中，慢指针 slow 向前移动一步 (slow = slow->next)。

• 快指针 fast 向前移动两步 (fast = fast->next->next)。

• 这样，当快指针到达链表的末尾时，慢指针正好位于链表的中间位置。

• 如果链表长度为奇数，fast 会停在链表的最后一个节点；如果链表长度为偶数，fast 会停在 NULL。在这两种情况下，slow 都恰好指向中间节点或第二个中间节点。

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

特别值得注意的是：while循环中的条件 (fast && fast->next)顺序不能改变，即（fast->next && fast）是错误的写法！因为当链表长度为偶数时，fast刚好停在NULL的地方，此时如果对fast解引用会出现对空指针解引用的操作，必然出错！

五.结语

       本文总结了三道单链表相关的经典面试题，它们分别考察了链表的增删、反转和查找操作。通过对这三道题的深入学习，我们不仅掌握了不同的解题方法，更重要的是理解了链表操作的核心——对指针的灵活运用。掌握了这些基础知识，你就能更好地应对更复杂的链表问题。希望这些内容能对你的学习和面试准备有所帮助！如果你有任何疑问或想探讨更多链表问题，欢迎在评论区留言交流。

文章来源于互联网:66链表三连击：面试官最爱考的三个单链表问题，你真的会吗？

相关推荐: 【百度拥抱开源】百度开源文心一言视觉大模型—— ERNIE-4.5-VL

ERNIE 4.5 技术亮点 ERNIE 4.5系列模型（特别是基于混合专家系统的A47B与A3B架构）的卓越能力源于以下核心技术创新： 多模态异构MoE预训练：通过文本与视觉模态的联合训练，模型能更精准捕捉跨模态信息的细微差异，显著提升文本理解生成、图像解析…