链舞算法谱---链表经典题剖析

前言：探究链表算法的奥秘，解锁编程新世界！

欢迎来到我的链表算法博客，这将是您深入了解链表算法，提升编程技能的绝佳机会。链表作为数据结构的重要成员之一，其动态性和灵活性在实现某些功能上发挥不可替代的功效。

本篇博客致力于揭秘链表算法的奥妙，分享实用的学习经验，仅供个人参考。我也希望您能独立实现代码完成相关的题型，还要尝试一题多解，发散思维。

如果对您有帮助，希望您能点赞关注作者，作者会持续输出新鲜干货，尽请期待！

前面，我们学习单链表的基本实现，比如链表的创建，销毁，增删查改等。

如果您不是很了解单链表的相关操作，可以读一下鄙人的单链表博客，或者自行学习。

数据结构篇其二---单链表（C语言+超万字解析）-CSDN博客

我们要注重理论实践结合，阅读他人的代码和相关题解（力扣网站每道题都有大佬（官方）的优秀题解供我们学习），更能熟悉掌握链表的核心知识。

本期精选链表算法的高级话题，选自力扣网站（后面附带刷题链接）。如反转链表，环形链表检测，链表相交，合并有序链表，移除链表元素，分割链表等一系列好题。

编程语言：C语言。

学习方法：

学习数据结构要多画图分析，一步一步来，能积微者速成。

一切条件判断，循环条件不知道怎么写的情况，都是因为图没有画清楚，逻辑没捋清楚。自己动手画比脑补来的快。

前言：探究链表算法的奥秘，解锁编程新世界！

一、反转链表（简单）

思路一：（三指针法）取节点头插。

思路二：（三指针法）直接反转

思路三：（三指针法）思路一的优化版本

二、移除链表元素（简单）

思路一：（双指针法）直接删除值为val的节点。

思路二：创建新链表

三、链表的中间节点（简单）

思路一：计算链表长度确定中间结点

思路二：快慢指针法

四、删除链表的倒数第k个节点(中等)

思路一：快慢指针法

五、返回倒数第k个节点（简单）

六、合并两个有序链表（简单）

思路一：创建新链表尾插

七、链表分割（较难）

思路一：先分割再合并（简单的思路）

八、链表的回文结构（简单）

思路一：中间节点+反转链表+双指针法

思路二：数组（换种数据结构）+双指针（对撞指针）

九、相交链表（简单）

思路一：暴力遍历。

思路二: （类似）快慢指针

十、环形链表（简单or难？）

思路一：快慢指针法

结尾

一、反转链表（简单）

据说这是面试出镜率最高的链表题。

206. 反转链表 - 力扣（LeetCode）

这里提供了三组示例供我们实际测试代码。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    
}

代码通过注释的方式给了我们结构体的声明，接着让我们实现函数内部的逻辑。

先分析函数和返回类型吧。

返回值：struct ListNode* 结构体指针，这里返回反转链表后的头指针。

函数参数：就一个参数，传入源链表的头指针。

下面提供几种思路。

思路一：（三指针法）取节点头插。

链表的元素是节点。我们就有第一种想法，将每个节点一个一个取下来进行头插。

同时考虑多种情况不符合人脑逻辑，我们先考虑第一种示例，再完善整体的逻辑。

怎么做呢？先分析已知指针的指向。

只有一个头指针指向链表的第一个节点。我们要实现把节点依次取下来进行头插的操作。显然只有头指针是不够的，我们再创建节点（结构体）指针。

那么创建几个结构体指针呢？

首先，我们处理链表问题，不会轻易动用头指针，除非链表的第一个节点改变了，才需要改变头指针指向。

所以要第一个头指针prev。如下图：

这样有了prev也指向第一个节点，就不要动head指针遍历链表了。

那么如何一个节点指针够了吗？

还是回归到问题上，我们要取下每个节点进行头插。

请阅读下面的代码和观察下面的图

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。
}

很遗憾只通过prev指针把第一个节点取下来了，但是第二个节点的位置找不到了。起不到头插的作用。

所以还需要个next的节点指针，指向取下节点的下一个节点。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。

    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。
}

取第二个节点的情况

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。

    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。

    //取第二个节点
    prev = next;//先让prev指向原链表的第二个节点。
    next = prev->next;//代码同取下第一个节点的情况。
    prev->next = NULL;

    //执行头插操作
    prev->next = head;//连接第一个节点
    head = prev;//头插改变头指针的指向。


}

那么后面规律自然清晰可寻了，我们这里考虑结束的情况。

选择什么循环和循环条件是什么问题就迎刃而解了。

按照前面的逻辑

prev跟上next，即prev=next;

next指向原先链表尾结点的指针指向部分，即next=NULL;

连接节点，prev->next=head;

再调整头指针的指向，即head=prev;

最终结果出来了，这个时候的head和prev指向新链表（反转链表）的第一个节点。next指向空，可作为循环条件。

最终结果如图：

代码就可以写了

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。

    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。

    while (next)
    {   
        //取第二个及之后的节点
        prev = next;
        next = prev->next;
        prev->next = NULL;
        //头插
        prev->next = head;
        head = prev;
    }
    return head;


}

提交一下。

挫折才是算法题的常态，不急看看红字说什么。

原来是空链表的情况啊。也就是题目所给示例3的情况。

最前面直接加个if判断就行了，空链表直接让他返回空指针就🆗了。

最终代码实现

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。

    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。

    while (next)
    {
        prev = next;
        next = prev->next;
        prev->next = NULL;

        prev->next = head;
        head = prev;
    }
    return head;


}

用时方面击败了100%的人，鼓励自己一下。

由于代码已经通过了，示例二我就不多说了，需要请您自行梳理。

思路二：（三指针法）直接反转

直接改变指向如何实现呢？

三指针。三个指针能改变朝向，双指针只能改变一次，不能循环起来。

第一步：

断开节点1和节点2，节点一指向n1;

第二步：

按顺序n1指向n2，n2指向n3，n3指向下一个节点（n3->next）;

接下来判断循环结束条件。

需要注意一次只改变一个节点的指针部分的指向。节点1和节点2只是断开了，节点1指向了空，并没有让节点2指向节点1。

循环结束条件为n2为NULL。

需要注意在连接最后一个节点时，n3已经为空指针了，不能再往后挪，即n3=n3->next;

补充：->结构体指针访问操作符，本质是指针解引用访问结构体的成员。而空指针不能解引用，会报错。

最后前面写个if语句，如果是空链表直接返回NULL。

struct ListNode* reverseList(struct ListNode* head) {
    if (NULL == head)//空链表
        return NULL;

    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;

    while (n2)
    {
        n2->next = n1;
        n1 = n2; 
        n2 = n3;
        if (n3)//尾结点改变连接朝向，n3已经为NULL，不能再解引用。
            n3 = n3->next;
    }

    return n2;
}

思路三：（三指针法）思路一的优化版本

思路一要修改原先的head，虽然和思路一思想一样，但重新创建一个新头指针，创建一个新链表，可读性好一些。

 struct ListNode* reverseList(struct ListNode* head) {
      struct ListNode* cur = head;
      struct ListNode* newhead = NULL;//定义新的头指针。
      while (cur)
      {
          struct ListNode* next = cur->next;//循环内部创建不用额外判断空链表的情况。
          cur->next = newhead;
          newhead = cur;
          cur = next;
      }
      return newhead;
  }

二、移除链表元素（简单）

203. 移除链表元素 - 力扣（LeetCode）

本题还是给了三组测试用例，我们先从第一组开始分析。

第一组样例：

思路一：（双指针法）直接删除值为val的节点。

要做到直接删除，至少要用两个相邻指针做到。

prev->next=pcur->next;//指向值为val的下一个节点

pcur=prev->next;//pcur指向

结束条件：

这里可用pcur作为循环结束的条件。

看不明白请自行画图分析。

 struct ListNode* removeElements(struct ListNode* head, int val) {
     struct ListNode* prev = NULL;
     struct ListNode* pcur = head;
     while (pcur)
     {
         if (pcur->val == val)//当前pcur所在节点值为val,执行删除
         {
             prev->next = pcur->next;
             free(pcur);
             pcur = prev->next;
         }
         else//pcur指向节点值不为val,prev，pcur整体往下一个节点走。保证它俩紧挨着。
         {
             prev = pcur;
             pcur = pcur->next;
         }
     }
     return head;//返回头指针
 }

接下来第二组和第三组测试用例

第二组给了空链表的示例，由于直接最前方写个if分支直接return NULL;

  if (NULL == head)
      return NULL;

第三组测试用例：

由于第一个节点就符合条件，而此时prev还为NULL，prev->next的行为会报错。

这种情况就要用单链表头插的思路，即head和pcur实现了

这种全符合 val的情形，只有head和pcur在动，没prev什么事了。

🆗，总结一下先判断要不要进行头删，直到第一个节点不在删除就得动用prev和pcur来进行一般的删除（第一组用例的方法）。

综合一下三组用例：最终代码实现

struct ListNode* removeElements(struct ListNode* head, int val) {
    //空链表直接返回。
    if (NULL == head)
        return NULL;
    struct ListNode* prev = NULL;
    struct ListNode* pcur = head;
    //判断要不要头删。
    while (pcur->val == val&&pcur!=NULL)
    {
        head = pcur->next;
        free(pcur);
        pcur = head;
        if (pcur == NULL)//如果全是val的情况，全部执行头删，pcur将为空，判断一下
        {
            return NULL;
        }
    }
    //第一个节点不是val启动prev,pcur，遍历链表进行删除。
    while (pcur)
    {
        if (pcur->val == val)//当前pcur所在节点值为val,执行删除
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
        }
        else//pcur指向节点值不为val,prev，pcur整体往下一个节点走。保证它俩紧挨着。
        {
            prev = pcur;
            pcur = pcur->next;
        }
    }
    return head;//返回头指针
}

看来情况考虑全了。

下面提供另一种思路：

思路二：创建新链表

虽然说是创建新链表，实际并没有增加新的节点。

一个新链表（单链表）有头有尾。

 //创建新链表
 struct ListNode* newhead = NULL;
 struct ListNode* newtail = NULL;

接下来我们要遍历原链表，找到值不为val的节点取下来进行尾插。
  struct ListNode* pcur = head;//引入一个指针变量，遍历整个链表
第一步：

由于第一个节点val值为1，取下来。
  newhead = pcur;
  newtail = pcur;
第二步：

pcur向后遍历，且让取下来的第一个节点指向空。因为单链表最后一个节点必须指向空，不然会出问题。
 pcur = pcur->next;//往下继续遍历。
newtail->next=NULL;//新链表尾指针指向空
第三步：

由于第二个节点val值为2，也取下来。看下图
  newtail->next = pcur;
  newtail = newtail->next;
第四步：

pcur继续向后遍历，且让取下来的第二个节点指向空。结合上图分析。
pcur=pcur->next;
newtail->next=NULL;
到这里规律就很明显了。

首先是pcur遍历原链表，pcur指向原链表的空指针说明循环结束。

pcur->val不满足指定val就尾插到新链表，此时又分两种情况，即第一次插入和后面的插入。第一次插入要修改头指针，使头指针指向第一个节点。后面进行尾插，只需要后一个节点连接前一个节点，并移动尾指针即可。

然后，若pcur->val满足指定val，就释放该节点，继续往后遍历。

需要注意的是，将节点取下来只是个形象的说法，本质就是新链表的头尾指针指向原先的节点。每次满足条件的节点取下来其指针部分指向要改为空。

如果觉得文字看不明白的话

请您自己画图配合看一下下面的代码吧。

struct ListNode* removeElements(struct ListNode* head, int val) {
    //该代码逻辑上包含了空链表，不用单独判断了。
    struct ListNode* newhead = NULL;
    struct ListNode* newtail = NULL;
    struct ListNode* pcur = head;
    while (pcur)//遍历原链表
    {
        if (pcur->val != val)//不满足指定val
        {
            if (NULL == newtail)//新链表第一次插入节点
            {
                newhead = pcur;
                newtail = pcur;
            }
            else//后面的插入，和单链表尾插相同的思路
            {
                newtail->next = pcur;//连接前一个节点
                newtail = newtail->next;//改变尾指针的指向
            }
            pcur = pcur->next;//往下继续遍历。
            newtail->next = NULL;//尾指针指向空，保证新链表（单链表）不出错
        }
        else
        {
            struct ListNode* del = pcur;//临时指针存储满足值为val的节点
            pcur = pcur->next;//继续遍历
            free(del);//释放满足条件的节点

        }
    }
    return newhead;
}

三、链表的中间节点（简单）

876. 链表的中间结点 - 力扣（LeetCode）

思路一：计算链表长度确定中间结点

这种思路很简单，引入int len；先遍历链表计算链表的长度，再遍历找到中间节点并打印。

链表的长度是节点的个数。

把链表元素（节点）想象成数组元素下标的形式

比如下面是奇数个节点就是，链表长度为5,中间长度就是5/2==2（整数除法）。就是对应下标为2的节点，就是3.

对于链表长度是偶数，节点个数是偶数的情况呢。

这里链表长度是6，中间长度是6/2=3，对应下标为三的节点，是4。符合题意。

int k = len / 2;就是中间长度了。
 struct ListNode* middleNode(struct ListNode* head)
  {
      if (head == NULL)//空链表
          return head;
      int len = 0;//长度变量
      struct ListNode* pcur = head;
      while (pcur)//遍历求链表长度
      {
          pcur = pcur->next;
          len++;
      }
      pcur = head;//重置pcur
      int k = len / 2 ;//中间结点到起点的长度。
      while (k--)
      {
          pcur = pcur->next;
      }
      return pcur;//返回中间节点的指针
  }

思路二：快慢指针法

思路一方法很好理解，但由于要计算长度，终归要先遍历一遍数组。然后找中间节点，相当于又遍历了一遍。

下面介绍快慢指针法

快慢指针，广泛应用于大量的算法场景。

先介绍背景，这种方法在解决此题时，不用求链表长度，只需遍历一遍。

快慢指针

以单链表为背景

快慢指针指的是移动步长，正如名称所示，快指针走的快（单次走的步数多），慢指针走得慢（单次走的少）

什么又叫走的步数多和走的步数少呢？

先说快慢指针的定义
struct ListNode {
    int val;
    struct ListNode *next;
};
  struct ListNode* fast = head;
  struct ListNode* slow = head;
快慢指针这里是结构体变量，很显然 fast和fast->next类型一样，可以进行赋值操作。

那么fast->next->next呢？也是结构体指针类型。

好像明白了！

fast=fast->next;//走一步。

fast=fast->next->next;//走两步。

同一循环下，慢指针走一步，快指针走两步。快指针到终点，结束循环，慢指针才走到链表的一半，就是中间节点处。

实践开始：

先考虑题中给的第一组示例。

struct ListNode* middleNode(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;//空链表可用不上快慢指针，直接返回空即可
    }
    //定义快慢指针
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast->next)
    {
        slow = slow->next;//慢走一
        fast = fast->next->next;//快走二
    }
    return slow;//慢指针所指向的就是中间节点
}

做到这儿大多人已经迫不及待地提交了。

只过了一个测试用例，太惨了。观察一下上面的图，题目中给定的测试用例二我们还没测呢。

偶数情况下的循环结束条件是fast==NULL;

慢指针依旧指向中间节点。
struct ListNode* middleNode(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;//空链表可用不上快慢指针，直接返回空即可
    }
    //定义快慢指针
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast->next && fast)//补上偶数的情况
    {
        slow = slow->next;//慢走一
        fast = fast->next->next;//快走二
    }
    return slow;//慢指针所指向的就是中间节点
}
然后提交。

呃？怎么还是报错了，明明逻辑没有错啊？

好吧还是错了，问题肯定出在修改过的地方。

while (fast->next && fast)

逻辑与是从左向右计算表达式的结果的。若fast已经为NULL，它会先进行左边的判断fast->next,显然会报错。应该先判断fast是不是NULL，在判断fast->next。

while ( fast 　&&　fast->next )
struct ListNode* middleNode(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;//空链表可用不上快慢指针，直接返回空即可
    }
    //定义快慢指针
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)//奇数个节点和偶数个节点的情况
    {
        slow = slow->next;//慢走一
        fast = fast->next->next;//快走二
    }
    return slow;//慢指针所指向的就是中间节点
}
🆗，思路二及原理讲解和可能遇到的问题就解决了。

四、删除链表的倒数第k个节点(中等)

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路一：快慢指针法

此题和链表的中间节点都可采用快慢指针法，只不过用快慢指针的方式不同。

快慢指针不一定比谁走得快，而可以认为谁走得远。

slow负责找倒数第k个节点，fast领先slow结束循环。

这里可以看到fast比slow多走了一步，可以用fast->next作为结束循环的条件。

那么这里有普遍的规律吗？

找倒数第二个节点，fast比slow多走一步。

找倒数第三个节点，fast同样指向尾结点，此时fast比slow多走两步。

找倒数第一个节点，fast同样指向尾结点，此时fast和slow相差0步

原来如此，找倒数第k个节点，fast要先走k-1步，然后再和slow一起走，符合快慢指针。

这里要执行删除操作，我们在定义一个prev指针循环找slow指向的前一个结点。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if (NULL == head)
        return NULL;
    struct ListNode* fast = head;
    struct ListNode* slow = head;
   
    int k = n-1 ;
    while (k--)//fast先走n-1步
    {
        fast = fast->next;
    }
    while (fast->next)//同时走
    {
        fast = fast->next;
        slow = slow->next;
    }
    struct ListNode* prev = head;//定义prev指针找slow的前一个结点。
    while (prev->next != slow)//找……ing
    {
        prev = prev->next;
    }
    //执行删除操作
    prev->next = slow->next;
    free(slow);

    //返回头指针。
    return head;

}

只过了一个测试用例？嗯冷静！

根据链表节点删除的经验，这种情况十有八九没考虑头删的情况。

下面分析一下不满足的测试样例。

 struct ListNode* prev = head;//定义prev指针找slow的前一个结点。
    while (prev->next != slow)//找……ing
    {
        prev = prev->next;
    }

明白了，这个时候prev和slow一样，要删掉头节点，这个循环不包括头删的情况。

那么用if_else语句分开讨论吧。

  struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
      if (NULL == head)
          return NULL;
      struct ListNode* fast = head;
      struct ListNode* slow = head;
     
      int k = n-1 ;
      while (k--)
      {
          fast = fast->next;
      }
      while (fast->next)
      {
          fast = fast->next;
          slow = slow->next;
      }


      //判断头删还是非头删的情况
      if (slow == head)
      {
          head = head->next;//修改头指针的指向即可。
      }
      else {
          struct ListNode* prev = head;//定义prev指针找slow的前一个结点。
          while (prev->next != slow)//找ing
          {
              prev = prev->next;
          }
          //执行删除操作
          prev->next = slow->next;
          free(slow);
      }

      //返回头指针。
      return head;

  }

时间上打败了全世界的人，加油！

总结

1.执行链表删除时考虑头删的情况。

2.考虑空链表的情况。

3.熟练快慢指针在此题的应用。

4.不用像作者那样试错，自己考虑完所有情况（画图分析），一遍过就完事。

遗漏的地方自己要独立分析完成。

五、返回倒数第k个节点（简单）

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

本题作为四题快慢指针的补充。

四题有过这幅图

下面我给出另一张图，分析一下区别。

结论就是循环条件不同，前者以fast->next==NULL结束，后者以fast==NULL,结束。

还有一个区别：前者fast比slow先走k-1步，后者fast先走k步。

🆗，我们用后者的形式快速解决这道题。

int kthToLast(struct ListNode* head, int k) {
    if (head == NULL)//空链表踢出跑步比赛资格
    {
        return NULL;
    }
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (k--)//fast先行k步
    {
        fast = fast->next;
    }
    while (fast)//fast和slow同时走，注意此时结束条件
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;//返回倒数第k个节点的val值
}

be far ahead

写得最快的一题。

六、合并两个有序链表（简单）

据说这是面试出镜率第二高的面试题。

21. 合并两个有序链表 - 力扣（LeetCode）

leetcode给的函数原型。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    
}

函数参数是两个链表的头指针，返回合并后链表的头指针。

思路一：创建新链表尾插

不需要复杂的套路，只要给我一个新链表的头指针和尾指针，我就能解决这道题。

由于目的是合并成升序表，原先的两个链表的节点两两对应比较，选择小的尾插，对应指针往后走一位。

如果是第一次尾插，需要注意newhead。

原先两个链表总有一个先走完；

再将剩下一个链表后面的节点相连即可。

nie

  struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
      //其中一个表为空表，合并结果就是另外一个表（无论其是否是空表）
      if (list1 == NULL)
          return list2;
      if (list2 == NULL)
      {
          return list1;
      }
      //创建新链表的头尾指针
      struct ListNode* newhead = NULL;
      struct ListNode* newtail = NULL;
      //循环结束条件，任一链表被排布完全。
      while (list1 && list2)
      {
          if (list1->val < list2->val)//比较两个有序链表各自当前节点大小
          {
              if (newtail == NULL)//第一次尾插
              {
                  newhead = list1;
                  newtail = list1;
              }
              else//后续的尾插
              {
                  newtail->next = list1;
                  newtail = newtail->next;
              }
              list1 = list1->next;
              newtail->next = NULL;

          }
          else
          {
              if (newtail == NULL)//第一次尾插
              {
                  newhead = list2;
                  newtail = list2;
              }
              else//后续尾插
              {
                  newtail->next = list2;
                  newtail = newtail->next;
              }
              list2 = list2->next;
              newtail->next = NULL;
          }
      }
      //尾指针直接连接剩下没填完链表的节点
      if (list1 != NULL)
      {
          newtail->next = list1;
      }
      if (list2 != NULL)
      {
          newtail->next = list2;
      }
      return newhead;//返回新链表的头指针。
  }

七、链表分割（较难）

链表分割_牛客题霸_牛客网 (nowcoder.com)

思路一：先分割再合并（简单的思路）

本题难点在于不能改变原来的数据顺序。

这里没给测试用例，我们这里假设原链表为{3 ，4，6，1，4，5，2，8}，其中x为4。

那么按照题意将小于x和大于等于x的分割在两边。

3，1，2 4，6，4，5，8

注意顺序不能变。

其实上面已经给定了思路。就是将原链表分割成两个链表，再将两个链表的尾和头连接起来。

这里为了方便，先将哨兵位（头节点）的概念，因为我单链表没涉及哨兵位的东西，所以这里默认大家不知道的情况。

有时候，为了方便，我们会在第一个节点前附带一个节点，称这个节点为头节点（哨兵位）。

这里我们可以重新定义空链表了。

原先我们认为空链表不带任何节点，其实这句话是针对不带头节点的链表。

由于头节点的数据域不会存储有效的数据（有效情况可以利用这个存储比如链表的长度什么的），指针域会存储NULL（针对空表）。

那么广泛的空表可以认为没有任何有效数据的节点。

这里头指针不在指向第一个节点，而是指向头节点（哨兵位）。

头节点和第一个节点是不一样的东西（虽然文字上相同），这里把头节点称为哨兵位更合适，不易混淆。

为什么要介绍哨兵位的概念？

至少我们了解一点，再进行尾插和头插相关插入数据的操作时，如果是不带哨兵位的空链表，那么最初头指针指向NULL，这种就要分情况讨论（第一次插入和第二次插入）。而带哨兵为的单链表，至少有一个节点，像桥梁一样，方便我们进行尾插头插，而不用这么麻烦。

链表分割完了吗，还没有，必须确保每个节点的下一个指向。

由题意，我们要尾首连接这个两个链表。

lesstail->next=greaterhead->next;

确保尾指针指向空

greatertail->next=NULL;

由于创建了两个哨兵位，我们最好销毁哨兵位。

先把头指针指向改了：

pHead=lesshead;

释放哨兵位：

free(lesshead);

free(greaterhead);

下面开始写代码吧

此题牛客网不提供C语言的方式，我们就选择C++完成此题，因为C++兼容C.
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lesshead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* lesstail = lesshead;
        struct ListNode* greaterhead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* greatertail = greaterhead;

        struct ListNode* pcur = pHead;
        //链表分割
        while (pcur)
        {
            if (pcur->val < x)
            {
                lesstail->next = pcur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next = pcur;
                greatertail = greatertail->next;
            }
            pcur = pcur->next;
        }
        //两个链表的连接和尾部置空
        lesstail->next = greaterhead->next;
        greatertail->next = NULL;
        pHead = lesshead->next;
        free(lesshead);
        free(greaterhead);
        return pHead;
    }
};

八、链表的回文结构（简单）

234. 回文链表 - 力扣（LeetCode）

先分享我一开始的愚蠢想法。

哎，这不简单嘛？搞两个对撞指针不就行了吗。

一个从头，另一个从尾部开始。

然后我才意识道单链表的单向性。不过并没无功，开始尝试就已经迈向了成功。

思路一：中间节点+反转链表+双指针法

正如小标题所说，我们要借助先前的题的函数了

一、反转链表

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。

    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。

    while (next)
    {
        prev = next;
        next = prev->next;
        prev->next = NULL;

        prev->next = head;
        head = prev;
    }
    return head;


}

三、链表的中间节点

struct ListNode* middleNode(struct ListNode* head)
{
    if (head == NULL)//空链表
        return head;
    int len = 0;//长度变量
    struct ListNode* pcur = head;
    while (pcur)//遍历求链表长度
    {
        pcur = pcur->next;
        len++;
    }
    pcur = head;//重置pcur
    int k = len / 2;//中间结点到起点的长度。
    while (k--)
    {
        pcur = pcur->next;
    }
    return pcur;//返回中间节点的指针
}

需要注意反转链表的函数再反转链表后，尾指针会指向空。如下图所示

找中间节点的函数只会返回中间节点的指针。

这里可用迭代过程中，可用rightpcur==NULL终止这一过程。

struct ListNode* middleNode(struct ListNode* head)
{
    if (head == NULL)//空链表
        return head;
    int len = 0;//长度变量
    struct ListNode* pcur = head;
    while (pcur)//遍历求链表长度
    {
        pcur = pcur->next;
        len++;
    }
    pcur = head;//重置pcur
    int k = len / 2;//中间结点到起点的长度。
    while (k--)
    {
        pcur = pcur->next;
    }
    return pcur;//返回中间节点的指针
}


struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。

    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。

    while (next)
    {
        prev = next;
        next = prev->next;
        prev->next = NULL;

        prev->next = head;
        head = prev;
    }
    return head;


}
bool isPalindrome(struct ListNode* head) {
    struct ListNode* midhead = middleNode(head);
    struct ListNode* rightpcur = reverseList(midhead);

    struct ListNode* leftpcur = head;
    while (rightpcur)
    {
        if (rightpcur->val != leftpcur->val)
        {
            return false;
        }
        else
        {
            rightpcur = rightpcur->next;
            leftpcur = leftpcur->next;
        }
    }
    return true;
}

思路二：数组（换种数据结构）+双指针（对撞指针）

此题本质是判断会不会回文的问题。既然单链表数据结构不好判断。

我们就把单链表数据，拷贝一份放到数组上。

类似动态顺序表的写法，创建动态数组。

bool isPalindrome(struct ListNode* head) {
    int* arr = (int*)malloc(sizeof(int) * 4);//函数内部手动创建一个动态顺序表
    int size = 0;//当前有效数据
    int capacity = 4;//数据容量大小
    struct ListNode* pcur = head;
    while (pcur)//将单链表的数据拷贝到动态内存。
    {
        if (size == capacity)//看情况扩容
        {
            int newcapacity =2 * capacity;
            arr = (int*)realloc(arr, newcapacity*sizeof(int));
            capacity = newcapacity;
        }
        arr[size++] = pcur->val;
        pcur = pcur->next;
    }
    //动态数组下标当作指针使用
    int left = 0;//有效数据的左下标
    int right =size - 1 ;//有效数据的右下标
    while (left <= right)
    {
        if (arr[left] != arr[right])
            return false;//有一个对应位数据不等就不是回文。
        left++;
        right--;
    }
    return true;//都符合，是回文结构。
}

动态还要考虑扩容和节省空间，干脆不要空间了，节约时间，用静态顺序表吧。

bool isPalindrome(struct ListNode* head) {
    int arr[100000];//一次性开辟大的空间，刚好符合题目最大的数据个数
    int size = 0;//当前有效数据
    struct ListNode* pcur = head;
    while (pcur)//将单链表的数据拷贝到定长数组上
    {
        arr[size++] = pcur->val;
        pcur = pcur->next;
    }
    //定长数组下标当作指针使用
    int left = 0;//有效数据的左下标
    int right =size - 1 ;//有效数据的右下标
    while (left <= right)
    {
        if (arr[left] != arr[right])
            return false;//有一个对应位数据不等就不是回文。
        left++;
        right--;
    }
    return true;//都符合，是回文结构。
}

九、相交链表（简单）

160. 相交链表 - 力扣（LeetCode）

解决这道题分两步：

1.判断链表是否相交。

2.若相交返回交点节点的指针，否则返回NULL。

那怎么判断链表相不相交呢？

图中所给示例即为链表相交的情况。

链表不相交如图。

链表不相交和链表相交有什么能够显著的区别？

你说相交有交点，不相交没有交点呗。

有道理，但我们先判断是否相交，再确认交点是谁。

很明显，如果我们同时遍历两个链表，相交链表的尾结点是一样的，不相交的链表的尾结点不一样。

总结一下:判断相交即判断尾结点相等。

下面提供两种思路

思路一：暴力遍历。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    if (headA == NULL && headB == NULL)
    {
        return NULL;
    }
    struct ListNode* pcur1 = headA;
    struct ListNode* pcur2 = headB;
    while (pcur1->next)
    {
        pcur1 = pcur1->next;
    }
    while (pcur2->next)
    {
        pcur2 = pcur2->next;
    }
    if (pcur2 != pcur1)//判断两个单链表尾结点是否相等。
        return NULL;
    pcur1 = headA;
    pcur2 = headB;

    //暴力查找
    while (pcur1)//嵌套while循环，A链表和B链表的所有节点一一比较。
    {
        pcur2 = headB;
        while (pcur2)
        {
            if (pcur2 == pcur1)
            {
                return pcur2;
            }
            pcur2 = pcur2->next;
        }
        pcur1 = pcur1->next;
    }
    //置空
    pcur1 = NULL;
    pcur2 = NULL;
    //找不到就返回空。
    return NULL;
}

其实这么些不用判断相不相交，我都暴力查找了。

时间复杂度o(n*n) 或o(n*m),删掉前面两个while循环也可，但是杯水车薪，稍微节约点时间。

思路二: （类似）快慢指针

还是这张图

我们其实可以一眼看到这叫交点就是C1,要是这两个链表一样长就好了，这样同时走，第一次节点地址相同就确定交点了，可惜这不是一样长的链表。

先不要叹气，思路不就有了吗？

我们模拟成等长链表不就行了吗。

链表有长有短，定义两个指针指向各自的头节点，让长的链表指针先走，走到等长的位置，然后两个指针同时走就行了啊。这种是不是和四、五题的快慢指针有异曲同工之妙。

整理一下思路

1.判断是否相交。

2.计算链表的长度差。

3.判断哪个是长链表。

4.定义双指针，长链表先走，然后同时走，第一次相遇即交点。

开始写代码。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    //判断空链表，任一一个为空必然不相交，虽然题目条件不包括空链表的情况。
    if (headA == NULL && headB == NULL)
        return NULL;
    struct ListNode* pcur1 = headA, * pcur2 = headB;
    int lenA = 1, lenB = 1;//记录长度变量

    //找尾结点，并计算长度
    while (pcur1->next)
    {
        pcur1 = pcur1->next;
        lenA++;
    }
    while (pcur2->next)
    {
        pcur2 = pcur2->next;
        lenB++;
    }
    if (pcur1 != pcur2)
    {
        return NULL;
    }
    int gap = abs(lenA - lenB);//abs为整型的绝对值函数，计算长度差距
    struct ListNode* fastlist = headA;//快指针
    struct ListNode* slowlist = headB;//慢指针
    //假设不成立
    if (lenA < lenB)
    {
        fastlist = headB;
        slowlist = headA;
    }
    //快指针先走gap步。
    while (gap--)
    {
        fastlist = fastlist->next;
    }
    //同时走
    while (fastlist)
    {
        fastlist = fastlist->next;
        slowlist = slowlist->next;
        if (fastlist == slowlist)
        {
            return fastlist;
        }
    }
    //为了防止不返回值，假装在这里返回空指针。
    //上面逻辑上肯定能返回值，非要搁这儿报错，只能在最后补上了。
    return NULL;
}

这道题搞定了。

时间复杂度o(n).

十、环形链表（简单or难？）

141. 环形链表 - 力扣（LeetCode）

先说一下循环链表的概念，前面的单链表称作单向不循环链表，不循环是什么意思呢？

单链表的尾结点指向NULL，即不循环。那么循环链表的概念就可以说，尾结点的下一个指针指向头节点的链表称为循环链表，如上图的示例一

而这里的示例一不难发现，尾结点的指针部分指向的是第二个节点，这就是一般的环形链表了。

下面我们关注此题如何解决？

很容易发现我们过去的迭代思路用不了了，因为对于在环形链表中循环，像之前那样写（如下代码），陷入死循环了。
while (pcur)
{
	pcur = pcur->next;
}
那具体怎么解决呢？判断走过一个节点两次？

好像不现实！再想想环形结构有什么特点。

环形结构是个圈吧。怎样判断自己的运动轨迹是圈？

在操场跑步的两个人，如果速度不一样，两个人一直跑，早晚会出现套圈的情况。而出现套圈这一情景，不就说明了操场的结构是环状结构吗。

对比在程序中，速度不一的两个人，不就是快慢指针吗？

快指针一次走两步，慢指针一次走一步。快指针先进环，慢指针后进环。两者出现相遇（套圈）就证明这是环状结构。

下面提供本题作者的唯一思路。其它方法自行搜leetcode题解

思路一：快慢指针法

bool hasCycle(struct ListNode* head) {
	if (head == NULL)//空链表取消比赛资格
		return false;
	struct ListNode* fast = head, * slow = head;//定义快慢指针
	while (fast)//若循环能结束，就说明非环状链表。
	{
		fast = fast->next->next;//快走二
		slow = slow->next;//慢走一
		if (fast == slow)//若是环状结构，快慢指针必向重逢。
		{
			return true;
		}
	}
	//非循环链表的情况。
	return false;
}

怎么又出错了，估计又出现空指针解引用的问题。

bool hasCycle(struct ListNode* head) {
	struct ListNode* fast = head, * slow = head;//定义快慢指针
	if (head == NULL)//空链表
		return false;
	
	while (fast&&fast->next)//若循环能结束，就说明非环状链表。
	{
		fast = fast->next->next;//快走二
		slow = slow->next;//慢走一
		if (fast == slow)//若是环状结构，快慢指针必向重逢。
		{
			return true;
		}
	}
	//非循环链表的情况。
	return false;
}

结尾

鉴于笔者写到这里神志不清了，影响创作质量，于是分期写完单链表的练习。

给您总结一下相关方法：

1.快慢指针法（双指针）

2.双指针和三指针。

3.弗洛伊德判环法（环形链表）//感兴趣可以自行了解。

转化思想，将复杂问题转化成曾经解决的问题或者易上手的问题。

下期更有极高价值的题，比如约瑟夫，环形链表II等，敬请期待。

好了作者要休息，感谢您的观看。