【数据结构之链表系列】链表常见OJ题汇总（持续更新）_链表常见题型

前言

本文主要总结博主平时做过的链表的常见OJ题，持续更新~

一、移除链表中的元素（多指针法）

1. 题目
   
2. 提交代码：
   
3. 提交结果：
   
4. 思路分析：
   本题主要是使用了三个指针来记录链表中的相邻三个结点，其中使用cur指针从头遍历到尾，使用prev指针随时记录cur的前一个结点，使用next随时记录cur的下一个结点。需要注意：当cur指针指向链表的第一个结点的时候，此时cur没有前一个结点，因此prev刚开始为空。在遍历的过程中，就是在不断比较cur指向的结点的值与题目给定的值是否相等，在这里就会分为两种情况，显然是cur指向的结点的值和题目给定的值是相等的，cur指向的结点的值与题目给定的值不相等。
5. 当cur指向的结点的值与题目给定的值不相等的时候，此时只需要让cur指针向后走，prev同步向后走即可，这里有一个细节，在cur向后走之前一定要先将cur的值更新到prev中，否则后续prev就无法更新了。
6. 当cur指向的结点的值与题目给定的值相等的时候，此时需要将cur指向的结点删除，这里又分为两种情况：prev是否为空，即删除的结点是否为第一个结点

• 当prev == NULL:此时删除的是链表中的第一个结点，在这里需要做的事情是删除第一个结点，更新头指针指向的结点到下一个结点，同时也让cur走向下一个结点，更新next,再更新next的时候一定需要注意此时cur是否为空，如果cur已经为空了，那么就不需要再更新Next了，这种情况发生在：更新cur前，cur已经指向链表的最后一个结点，那么此时Next指针就已经为空，此时更新cur指针的话，cur就为空了，所以此时不能再更新next指针，如果再更新next指针，就会在代码next - cur->next;中出现cur为空指针的情况继续访问空指针，处理方法就是由于注意到cur可能走向空，所以，再更新next指针之前需要判断cur指针是否为空
• 当prev!=NULL的时候：说明此时删除的结点不是第一个结点，那么此时需要做的事情就是删除cur指向的结点（free(cur);）,让cur前后指向建立练习（prev->next = next;）,再更新cur和next，再更新next的时候同样需要注意cur为空的情况需要额外进行判断

二、反转链表（多指针法&头插法）

1. 题目：
   
2. 多指针法

• 提交代码：
  
• 提交结果：
  
• 思路分析：
  本题采用三个指针来解决链表的反转问题，使用cur指针从头到尾遍历链表的每一个结点，使用prev指针随时记录cur指向的结点的前一个结点，使用next指针随时记录cur指针指向的结点的下一个结点，刚开始，当cur指向链表的第一个结点的时候，此时cur指向的结点没有前一个结点，此时prev = NULL;再从头遍历到尾的过程中，我们会发现，我们只需要将cur指向前一个结点，依次到尾，就会发现链表就被反转了，迭代的过程，先保存cur结点的下一个结点，然后先将cur的值更新给prev,再更新cur为next,更新cur的时候同样需要注意cur的值是否为空，当最后依次遍历的时候，也就是遍历链表的最后一个结点的时候，更新cur的时候cur就被更新为空指针了，此时就不需要再更新next了，处理方法同样是在更新next前先判断cur的值是否已经是空指针，若是，则不需要继续更新，若不是，则再继续更新next

2. 头插法（构造新链表）
   提交代码
   

• 提交结果
  
• 思路分析：
  本题也可以通过构造一个新链表采用头插法来解决：具体为构造一个新链表的头指针newHead，刚开始为空，使用一个cur指针遍历原来链表，使用next指针随时记录cur指针指向的结点的下一个结点随时准备更新cur,让cur指向新链表的头newHead,这样就可以不断将原链表的结点一个个连接到新链表，从而完成原链表的反转，再更新next的时候同样需要注意cur为空的情况，当遍历到原链表的最后一个结点的时候，此时next指向空，再更新cur,cur也指向了空，此时就不需要继续更新next了。

三、链表的中间结点（算数法和双指针法）

1. 题目：
   
2. 算数法

• 提交代码：
  

• 提交结果：
  

• 思路分析：
  通过先计算出链表中的结点个数，再计算链表的中间结点数，通过对链表的结点个数是奇数还是偶数进行分类讨论，从而确定返回的是哪个结点作为中间结点，注意在计算链表结点个数时，count变量应该从0开始进行计算，而不能从1开始，如果从1开始，就会导致计算出的结点个数多1，因为再遍历的过程中我们是控制遍历到空的，所以上面是一种方法：count从0开始，遍历到空，也可以：count从1开始，遍历到最后一个结点。上面的两种方法的控制就是在遍历中的循环条件不同而已。对链表结点个数进行分类讨论的过程中有两种情况：链表结点个数为奇数，链表结点个数为偶数

• 当链表结点个数为奇数时：此时只有一个中间结点，先求出中间结点数mid,然后使用循环条件–mid进行控制即可，cur从头开始的情况

• 当链表结点个数为偶数时：此时链表存在两个中间结点，根据题目要求，我们需要返回的是第二个中间结点，此时求出中间结点数之后，使用循环条件mid–进行控制即可，cur从头开始的情况

• 2. 双指针法

• 提交代码：
  

• 提交结果：
  

• 思路分析：
  本题采用快慢指针（双指针）的方法来解决求中间结点的问题，通过中间结点大概是总结点数的两倍的关系采用快指针一次走两步，慢指针一次走一步，慢指针最终记录的就是我们所要的中间结点，这个题同样需要对结点的个数进行分类讨论，当结点个数为奇数的时候，快指针走到最后一个结点的时候，此时慢指针记录的就是中间结点，当结点个数为偶数时，链表同样存在两个中间结点，当快指针走到空的时候，此时慢指针记录的就是我们想要的中间结点，需要注意的是while(fast&&fast->next)这个循环条件中fast和fast->next的位置不能颠倒

四、链表中的第K个结点（算数法&双指针法）

题目：

1. 算数法
   提交代码
   
   提交结果：
   
   VS上测试分析
   
   思路分析：
   算数法是通过求出链表总的结点个数，再算倒数第K个结点，比如：cur从头开始，一共有5个结点，倒数第1个结点其实就是第5个结点，倒数第2个结点就是第4个结点，倒数第3个结点就是第3个结点，倒数第4个结点就是第2个结点，倒数第5个结点就是第1个结点，循环的次数，当k = 1时循环4(5-1)次找到第5个结点，当k = 2时，循环3(5-2)次找到第4个结点…,当链表中结点个数为count时，cur从头开始，找倒数第k个结点需要循环（count-k）次

2. 双指针法
   提交代码：
   

提交结果：

思路分析：
对于给定的链表头指针，一定要注意判断链表为空的情况，这个情况一般在做题的时候需要单独进行分析，本题主要是采取两个指针来解决问题，这个题要求的是链表倒数第K个结点，这个K，我们可以理解为是一个相对距离，就是相对于链表最后连接的空指针的一个相对距离，也就是相对于链表连接的空指针k个结点的位置，比如：倒数第1个结点，其实就是相对于链表连接的空指针1个结点的结点，倒数第2个结点就是相对于链表连接的空指针2个结点的结点，因此基于这样的思路，我们可以考虑使用两个指针，一个是快指针，走在前面探路，一个是慢指针，在后面，在刚开始的时候，我们先让快指针走K个结点，此时快指针和慢指针之间的距离是K个结点，从此之后，快慢指针同步向后走，并且在此过程中，快慢指针之间的相对距离保持不变，为K个结点，当快指针走到空时，慢指针所指向的结点就是我们想要求的链表中倒数第K个结点。在做题的过程中，我们需要注意一些特殊的情况，就是如果K的值大于链表的结点个数，这种情况下，在快指针刚开始走K个结点的时候，就会导致快指针先走到空指针，因此，在这里，我们需要进行一些特殊的处理，如果快指针已经走到空指针了，那么就说明K的值大于链表的结点个数，此时是无法求链表倒数第K个结点的，所以我们需要返回空指针。

五、合并两个有序链表（尾插法）

题目：

提交代码：

提交结果：

思路分析：
本题采用归并思想结合构造新链表尾插的方法来解决问题，题目给定的两个待合并的链表可能会有几种情况，可能两个链表同时都为空，可能两个链表中一个为空，另一个链表不为空，所以一共有三种情况，我们在代码中刚开始的判断就可以很好地处理这个问题，如果第一个链表为空，不管第二个链表是否为空，我们都可以返回第二个链表，如果第二个链表为空，那么返回的就是空指针，如果第二个链表不为空，那么返回的就是第二个链表实际的数据，同样的道理，如果第二个链表为空，那么不管第一个链表是否为空，我们直接返回第一个链表，当第一个链表为空时，我们返回的就是空指针，当第一个链表不为空时，返回的就是第一个链表实际的数据。除此之外就是两个链表都不为空的情况了，这个时候是通过list1和list2分别遍历第一个链表和第二个链表，list1和list2分别都是从对应链表的第一个结点开始，如果list1(第一个链表遍历的指针)指向的数据小于list2(第二个链表遍历的指针)指向的数据，那么就将list1(第一个链表遍历的指针)指向的数据尾插到新构造的链表，如果list1(第一个链表遍历的指针)指向的数据大于等于list2(第二个链表遍历的指针)指向的数据，那么就将list2(第一个链表遍历的指针)指向的数据尾插到新构造的链表.在链表尾插的时候，如果链表是没有头结点的，一定要注意链表尾插的一个经典问题，尾插第一个数据的时候，此时链表的头指针和尾指针都是指向空指针，我们需要手动将链表的头指针改成第一个结点的地址，同时需要更新尾指针，如果尾插的不是第一个结点，那么只需要将指定的结点插到尾结点的后面即可。退出循环的条件，遍历的两个链表中一个已经遍历到空，一定是一个遍历到空，不可能是两个全部遍历到空，因为我们每次只取两个链表中的其中一个链表的一个结点，所以不可能出现两个链表同时遍历到空，此时，我们只需要将不为空的那个链表剩余的结点链接到构造链表的尾结点后面即可，最终返回构造链表的头指针。

六、链表分割（尾插法）

题目：

提交代码：

复习提交的代码：

提交结果：

思路分析：
本题建议采用带头结点的链表来解决问题，题目给出的是一个链表，同时给出一个值x，要求将链表以x为基准分割成两个部分，并且小于x的结点放在前面，大于等于x的结点放在后面，同时保持结点的相对顺序不变。我们的思路是将链表先分成两个部分，其中一部分是小于x的结点，另一部分是大于x的结点。我们考虑构造两个带头结点的链表，这里需要知道，头结点需要我们手动为其malloc空间，同时需要注意malloc空间之后需要对返回的地址进行强制类型转化和检查该地址是否为空，接下来的思路就是采用尾插法分别将原来链表的结点进行遍历按x为基准尾插到大小链表，当尾插完成之后，此时需要将两个链表链接起来，小链表的尾需要连接到大链表的头，这里我们需要注意，题目给的链表没说明默认给的是不带头结点的链表，因此我们在操作的时候一定要注意头结点的处理，在处理的时候需要注意一种特殊的情况，就是最后一个结点的值是比x小的，倒数第二个结点的值是比x大的，倒数第二个结点是连接到大链表，最后一个结点是连接到小链表，而此时我们发现，这种情况下，最后大链表最后一个结点中存储的地址没有修改，因此大链表最后一个结点指向的是小链表最后一个结点，所以，如果在这里我们没有对大链表最后一个结点中存储的地址进行修改的话，那就会出现连接后的链表出现带环的结构，从而后面会出现死循环，处理方法：将大链表的最后一个结点中存储的地址置成空指针。最后还需要注意头结点的释放，因为题目给的是不带头结点的链表，所以我们返回的肯定也要是不带头结点的链表，刚刚我们申请的是带头结点的链表，此时我们需要对构造的两个链表的头结点进行释放，否则会导致内存泄露。释放的时候需要先分别保存小链表和大链表真正存放数据的第一个结点，然后再释放其头结点。
建议使用带头结点的原因：

1. 在对链表进行分割的时候需要使用尾插，带头结点的尾插是不需要考虑插入第一个结点的特殊情况的，直接插在尾结点的后面即可
2. 原来链表中的数据可能会出现三种情况：

• 数据全部比x小：这种情况最后大链表会为空
• 数据全部比x大或者等于：这种情况最后小链表会为空
• 数据存在比x大和大于等于x的结点：这种属于常规情况
  综合上面出现的三种情况，在大小链表进行合并的时候就需要考虑很多情况，所以相比于带头结点的链表会复杂
  复习之后总结出的细节：
• 在使用malloc函数申请空间的时候，如果是结点中包含指针，一定要将指针进行初始化，如果不知道将指针初始化成什么内容，那么可以先将指针设置成空指针，如果没有对指针进行初始化，那么就会出现野指针的问题，后续容易产生程序崩溃
• 在本题最后的链表的连接中，一定要注意先将两个链表连接起来，再处理头，这个顺序一定不能反过来。如果我们先处理头，比如小链表中没有结点，那么我们这个预先返回的头就是一个控指针了，那么这个时候你再去将链表连接起来是没有办法改变这个头，这个头仍然是空指针。

七、链表的回文结构

题目：

提交代码：

提交结果：

思路分析：
本题综合采用求链表的中间结点和链表逆置两个算法来解决问题。基本思路：求出原来链表的中间结点，从中间结点开始，把中间结点及后面的结点看成是一个新链表，将该链表进行逆置。从该逆置链表第一个结点开始，依次与原来链表的对称位置上的结点的值进行对比，直到遍历到逆置链表为空，循环结束，在循环对比的过程中，如果出现对称结点的值不相等，则直接判断该链表不为回文结构，如果能够成功遍历到逆置链表为空，则说明该链表是回文结构。

八、链表相交

题目：

提交代码：

复习版本的代码（带详细注释）：

提交结果：

思路分析：
首先应该考虑两个链表是否为空的情况，如果只要有链表是空的，那么两个链表就不可能相交。接下来就要判断两个链表是否相交，只有相交的情况才需要找第一个公共点，找出两个链表的尾结点，判断两个链表的地址是否相等（两个链表的尾结点是否是同一个结点），如果尾结点是同一个结点，那么两个链表是相交的，如果尾结点不是同一个结点，那么两个链表不相交，因为两个链表相交的情况只可能是Y字形，不可能是X字形的，因为两个链表都是单链表。找第一个公共点，首先算出两个链表的结点个数，从而确定两个链表的差距，接下来就是确定两个链表谁长谁短，这里有一个技巧（假设法）：先假设其中一个链表是长链表，那么另一个链表是短链表，然后再通过反逻辑进行判断，也就是说假设不成立时就修改刚刚的条件。接下来就是先让长链表走差距步，再让两个链表同时向后走，当走到第一个公共点（地址相同的结点）时即找到第一个交点，比如：长链表比短链表长两个结点，那么我们再遍历找公共点的时候，先让长链表向后遍历两个结点，再让两个链表的遍历指针同步向后遍历，先让长指针走差距步的原因是为了，让它们能够再逻辑上的同一个起点一起往后遍历。

九、环形链表（一）

题目：

提交代码：

提交结果：

思路分析：
本题使用快慢指针的方法来解决问题，快指针的速度是慢指针速度的两倍，慢指针一次走一个结点，快指针一次走两个结点，如果链表中存在环，那么快指针是不会走到空的，如果快指针走到空，那么就说明链表中不存在环，因为链表的结点个数可能出现是奇数或者偶数，所以在循环条件判断的时候一定需要同时判断快指针和快指针的下一个结点是否为空，并且这里和我们求链表中间结点中使用的快慢指针的方法中的循环判断条件是一样的，快指针和快指针的下一个结点的位置不能颠倒。当快指针和快指针的下一个结点都不为空的时候，那么循环条件一直为真，所以在追及，及快指针在追及慢指针。因为快指针每次走两个结点，慢指针每次走一个结点，所以如果链表中存在环，那么肯定是快指针先进入环，慢指针后进入环，我们假设当慢指针进入环的时候，快指针和慢指针之间的追及距离是x，注意追击距离的判断，一定是快指针追击慢指针的方向，那么因为快慢指针之间的速度问题，所以每次追击都会使快指针和慢指针指向的距离减少1个结点，当快指针和慢指针之间的追击距离减少为0个结点的时候，此时快指针就追上慢指针，此时说明链表中是存在环的，也就是证明了同一个结点可以被二次遍历到。
上述是环型链表中的一个基本的题型，下面将阐述环形链表的一些拓展情况：

当快指针一次走三个结点，慢指针一次走一个结点时，快指针能够追上慢指针呢？
同样，因为快指针一次遍历的结点比慢指针快，所以显然快指针会先进入环，慢指针后进入环，我们假设当慢指针进入环的时候，此时快指针和慢指针之间的追击距离是x，因为快指针一次走三个结点，慢指针一次走一个结点，所以每次遍历，都会十快指针和慢指针之间的追击距离减少2个结点，所以快指针和慢指针之间的追击距离的变化情况为x,x-2,x-4,…,2,0.显然当x为2的倍数的时候，那么最终快指针会追上慢指针。如果x不是2的倍数，那么追击距离的变化情况：x,x-2,x-4,…,1,-1,…这种情况，我们假设链表中环的长度为C，当快慢指针之间的追击距离减少为-1，说明快指针超越了慢指针，也就是这两个指针错位了，此时快慢指针之间的追击距离变成了C-1，此时需要对C-1进行分类讨论，如果C-1为偶数，则最终追击距离会减少为0，则快指针可以成功追上慢指针。如果C-1不是2的倍数，则最终不会减少为0，这种情况下，快指针是没有办法追上慢指针的。

十、环形链表（二）

提交代码：

提交结果：

思路分析：
本题同样是采用快慢指针的方法来解决问题，首先先分类讨论，对一些特殊的情况进行单独处理

• 当链表为空时，不需要处理，直接返回空指针
• 当链表不为空时，且链表只存在一个结点，不可能存在环，所以返回空指针
• 当链表只有两个结点，并且存在环时，返回第一个结点的地址
• 当链表中存在2个以上结点时：首先分析链表中是否存在环，采用快慢指针的方法进行确定，前面已经证明过，当慢指针一次遍历一个结点，慢指针一次遍历两个结点时，如果链表存在环，则快指针一定会追上慢指针，即慢指针此时指向的结点可以被二次遍历到，说明链表中存在环，并且此时快指针追上慢指针，该结点为快慢指针在环中的第一次相遇结点，我们可以证明当一个指针从链表起点开始遍历，另一个指针从快慢指针相遇点开始遍历，两个指针同时以一次遍历一个结点的速度向后遍历，最终两个指针会在环的起始点相遇，下面将给出证明过程。
  证明：假设链表起点到环的起点的距离是L，环的起点到快慢指针的相遇结点的距离为X，环的长度是C。因为快指针的速度是慢指针速度的两倍，所以快指针的路程是慢指针路程的两倍，我们先求出快指针和慢指针的路程。快指针的路程：L+NC+X，慢指针的路程：L+X，我们要知道，当慢指针进环之后，快指针在一圈内一定会追上慢指针，因为当慢指针进环时，快指针和慢指针之间的追击距离最多是C-1，而快慢指针之间的追击距离每次都会减少1个结点，所以快指针在一圈之内一定会追上慢指针，所以慢指针的路程是L+X，由快慢指针之间的路程关系可得：L+NC+X = 2*（L+X），化简得：NC = L+X，也就是L = NC-X，即当一个指针从快慢指针的相遇点出发，另一个指针从链表起点出发，以每次一个结点的遍历速度往后遍历，最终会在环的起点相遇。

十一、复杂链表的复制：复制带随机指针的链表

题目：

提交代码：

提交结果：

思路分析：

这个题要我们复制一个复杂的链表，每一个链表的结点除了数据域和指向下一个结点的指针域之外，还有一个指向链表中随机结点的指针域。
思路：

1. 将每一个结点的拷贝结点连接到原来链表中对应结点的next指针上
2. 处理拷贝结点中的random指针，这里分为两种情况，原来链表中结点的random可能指向的是空指针，也可能指向的是链表中任意的非空结点

• 当原来链表中结点的random指针指向的是空指针，那么拷贝链表的结点指向的也是空指针
• 当原来链表中结点的random指针指向的不是空指针，而是链表中任意非空指针时，根据上面构造的结构（拷贝链表中的结点分别连接在原来链表对应的结点的后面），所以拷贝链表的结点的random指针应该指向原来链表中对应结点的random指针指向的结点的next指针指向的结点

3. 还原原来链表的指针指向状态和将拷贝链表中的结点连接起来
   首先需要一个cur指针从原来链表的头开始，依次找到对应的copy(cur->next)结点，然后保存cur在原来链表中的下一个结点next，也就是cur->next->next(copy->next),然后将cur->next指向此时的next(还原原来链表的结构),copy结点的next指向next->next(由上面构造的结构可以知道)，在连接的时候同样需要知道一种特殊的情况，当处理的是原来链表中的最后一个结点(cur->next = NULL),此时下一个指针是空了,此时copy的next也指向空就可以了。

本题在最后一步处理的过程中除了直接在原来构造的结构上处理之外还可以灵活采用构造新链表尾插的方法来处理：

即遍历原来链表分别找到对应结点的拷贝结点，然后将对应的拷贝结点连接到一个新的空链表上，最终返回这个新的链表的头即可。