前言
学习完了链表结构，不妨多加练习熟系这种数据结构。所以本篇论文列举出了一些和链表相关的练习题，并描述解题思路，相信对能够令读者对链表这种结构的掌握更加得心应手。
一、链表练习题
1. 输入一个链表，输出该链表中倒数第k个结点。 OJ链接
1.1. 题目描述
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2 输出： 4
说明：给定的 k 保证是有效的。
1.2. 题解思路
从题目的描述中可以得知，我们需要返回倒数第k个节点，如果可以从后向前遍历，那么这个题目会简单不少，但是链表为单向无头不带环链表，结构如下所示：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/因此我们需要用其他的方法来解决这个问题。
在做这个题的时候如果做过找链表中间节点的题的话，我们可以借用这道题的思路做一个快慢指针出来，根据示例的图示如下：
图1-1快慢指针法
思路如图1-1所示，先让快指针走k步，然后让快指针和慢指针一起走。当快指针走到NULL节点的时候，慢指针正好到达指定位置——倒数第k个节点。
1.3. 解题代码
根据1.2.的思路，解题代码如下：
int kthToLast(struct ListNode* head, int k){
struct ListNode* slow = head;
struct ListNode* quick = head;
//快指针先走k步
while(k--)
{
quick = quick->next;
}
//快慢指针一起向前走，直到快指针到NULL节点
while(quick)
{
quick = quick->next;
slow = slow->next;
}
//返回慢指针
return slow->val;
}代码提交结果如下：
因此解题思路和代码都没有问题。
2. 链表的回文结构。OJ链接
2.1. 题目描述
描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
2.2. 题解思路
和第一题一样，这一题也是单向链表，那么我们就不能从后往前访问了。那么为了达到能够同时向前向后访问，有两种思路：（1）把链表后半段逆至。（2）把链表数据拿出来放到能够反向找数据的结构中，比如数组。
2.2.1. 把链表后半段逆至
这个思路就是先用块慢指针，慢指针一次走一步，快指针一次走两步。找到中间节点，然后将后半段逆至，最后同时从前从后遍历并依此比较。全部相等就返回true，有一个不同就返回false。图解如下：
图2-2 找到中间节点
如图1-2，能够找到中间节点，随后逆至后半段节点，用三个指针，图解如下：
图2-2 逆至节点
如图1-3所示，逆至的后半段节点，剩下的就是同时向前向后遍历，比较节点的值了，如图1-3所示：
图2-3 同时遍历
2.2.2. 把链表数据拿出来放到能够反向找数据的结构中，比如数组。
思路其实从题目中也能知道，首先创造一个数组，当然也可以用之前顺序表的数据结构。如果用的是数组还需要定义一个变量记录有多少个数字，每录入一个数字就++。图解如下：
图1-4 将链表中数据存入数组
然后前后同时比较就行了。图解如下：
图1-5 两个节点比较并分别向对侧移动
2.3. 解题代码
本题解题代码采用方法1，将三个步骤分别分装为三个函数，代码如下：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//找到中间节点
ListNode* GetMid(ListNode* A)
{
ListNode* slow = A;
ListNode* quick = A;
//当快指针到末尾或者下一个节点是空就结束循环
while(quick && quick->next)
{
slow = slow->next;
quick = quick->next->next;
}
//返回中间节点
return slow;
}
//翻转后半部分链表
ListNode* GetReturnMid(ListNode* A)
{
ListNode* cur = nullptr;
ListNode* prev = nullptr;
ListNode* next = A;
//三个指针，next到空就结束循环
while(next)
{
prev = cur;
cur = next;
next = next->next;
cur->next = prev;
}
//返回末尾的节点
return cur;
}
bool chkPalindrome(ListNode* A) {
//接收中间节点
ListNode* mid = GetMid(A);
//找到末尾节点
ListNode* start2 = GetReturnMid(mid);
//头结点
ListNode* start1 = A;
//当末尾节点到空就结束循环，后半段一定短于前半段
while(start2)
{
if(start2->val != start1->val)
{
//比较有不同的数，链表不是回文
return false;
}
start2 = start2->next;
start1 = start1->next;
}
//全部相同，链表是回文
return true;
}
};最后提交代码结果无误，截图如下：
3. 相交链表
3.1. 题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
3.2. 题解思路
我们需要确认链表是否有交点那么但是却只能遍历链表，没有到交接处的长度也可能互不相等，那么就可以有以下多种状况：
图3-1 状况1
图3-2 状况2
图3-3 状况3
有可能A长，有可能B长，也有可能一样长，最后也会不相交。所以没办法确认需要走的长度。所以我们就找相交链表的共通点，那就是相交链表的最后节点地址一定是相同的，所以可以分别遍历两个链表开头，如果最后节点地址相同就能证明两个链表相交。
已经确认相交了，那么怎么找到链接的节点呢？这个时候就可以计数，看链表的长度如何，最后相减，然后让长的一方先走多出来的步数，这样就能够确认两个链表同时走到链表链接处了，也可以随时比较。最后返回链接的节点即可。
3.2. 解题代码
分析如上所示，分装了三个函数，代码如下：
// 判断链表是否相交
bool GetListSize(int* Asize, int* Bsize, struct ListNode *headA, struct ListNode *headB)
{
//遍历链表找到最后节点
while(headA->next)
{
++*Asize;
headA = headA->next;
}
while(headB->next)
{
++*Bsize;
headB = headB->next;
}
//判断最后节点是否相同
if(headA != headB)
{
return false;
}
else
{
return true;
}
}
//计算长链表事先走的步数
int Abs(int a, int b)
{
int dif = a - b;
if(dif >= 0)
{
return dif;
}
else
{
return -dif;
}
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int listsizeA = 0;
int listsizeB = 0;
//进入函数，判断链表是否相交，相交返回true
if(!GetListSize(&listsizeA, &listsizeB, headA, headB))
{
return NULL;
}
//假定A链表是短链表
struct ListNode* shortlist = headA;
struct ListNode* longlist = headB;
//如果实际大小相反，则转换B链表为短链表
if(listsizeA > listsizeB)
{
shortlist = headB;
longlist = headA;
}
//计算长链表事先走的步数
int dif = Abs(listsizeA, listsizeB);
//移动指向长链表的节点
while(dif--)
{
longlist = longlist->next;
}
//同时移动长短链表的节点，找到相同的节点
while(longlist != shortlist)
{
longlist = longlist->next;
shortlist = shortlist->next;
}
//返回节点
return shortlist;
}代码执行结果如下：
结果无误。
4. 拷贝链表， 返回链表的深度拷贝。OJ链接
4.1. 题目描述
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
4.2. 题解思路
4.2.1. 思路1——反复遍历找到随机指针的位置
深度拷贝那么就不能在原来链表上下太多功夫，我们可以直接先复制出来一个链表，先不管随机指针指向的位置，先深度拷贝链表。然后再来解决随机指针的问题。
因为原来的链表和直接深度拷贝的链表没有关系，所以随机指针的找法就是遍历。如何遍历呢？首先判断随机指针是否为空，为空就指向NULL，反之就定义两个指针指向两个链表的头，由原链表的节点来控制拷贝链表节点的位置，一起向后遍历，找到了就将拷贝链表的随机指针链接上指定位置。
图4-1 链表传统深拷贝
这种方法的缺陷就是时间复杂度为O(N^2)，链表节点假设有个百万级超时是妥妥的。
4.2.2. 思路2——让拷贝链表和原链表建立联系
这种思路就是先把拷贝节点插入到原链表对应节点之后，如图所示：
图4-2 链表分别拷贝节点并链接
这样拷贝的好处就是能够更快的找到随机指针，原链表的节点一定是隔一个在中间，所以先分别找到原节点对应的拷贝节点，通过找到原节点的随机指针，那么下一个就是该拷贝节点所指向的位置。
图4-3 拷贝链表找到随机指针
当然还需要先判断随机指针是否是空指针，不然去找空指针的下一个位置是会报错的。最后就将链表恢复原样即可, 时间复杂度是O(N).
4.3. 解题代码
这里代码采用思路2的思路，代码如下：
// 建立一个新节点
struct Node* BuyNode(int x)
{
struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
if(newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->val = x;
newnode->next = newnode->random = NULL;
return newnode;
}
struct Node* copyRandomList(struct Node* head) {
//为空直接返回
if(head == NULL)
{
return NULL;
}
//在原节点的下一刻创造拷贝节点
struct Node* cur = head;
while(cur)
{
struct Node* newnode = BuyNode(cur->val);//创立新节点的函数
newnode->next = cur->next;
cur->next = newnode;
cur = newnode->next;
}
//重置cur指针
cur = head;
//让curnext指向拷贝的节点
struct Node* curnext = head->next;
// 找到拷贝节点随机指针指向的位置
while(cur)
{
//随机指针为空就直接赋为NULL
if(cur->random == NULL)
{
curnext->random = NULL;
}
else//反之就赋值为原链表随机指针的下一个
{
curnext->random = cur->random->next;
}
//原指针向下遍历
cur = curnext->next;
//如果原指针已经为空了就没有下一个拷贝指针了
if(cur)
{
curnext = cur->next;
}
}
//重置节点
curnext = head->next;
//这个节点用来记录拷贝节点的头结点
struct Node* list = curnext;
//将原链表和拷贝链表分别链接
for(cur = head; cur; )
{
//链接原链表
cur->next = curnext->next;
//移动指针到原链表下一个节点
cur = curnext->next;
if(cur)
{
//如果原链表之后还有节点，就链接拷贝链表
curnext->next = cur->next;
//移动到下一个位置
curnext = cur->next;
}
else
{
//如果原链表指针到末尾了，直接将拷贝链表最后节点的下一位置空
curnext->next = NULL;
}
}
//返回拷贝链表头结点
return list;
}代码执行结果如下，结果无误：
二. 带环链表练习题
5. 给定一个链表，判断链表中是否有环。 OJ链接
5.1. 题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
5.2. 题解思路
首先判断没有环很简单，如果节点遍历到最后能够为空，就说明链表节点中没有环。相反，如果有环的话就遍历不到空节点。在有环的时候也伴随着一个问题，那就是如果找到空节点才结束遍历，那么带环的链表就结束不了循环。所以本体的难点在于如何结束带环链表的遍历。
一个指针解决不了，就两个指针。采用快慢指针的思路，快指针一次走两步，慢指针一次走1步，这样根据1步的速度差，进如环内快指针总会追上慢指针。
图5-1 带环节点遍历举例
还有一些额外的问题。
5.2.1. 快指针会不会碰不到慢指针
从结论来说，在带环链表中如果慢指针走一步，快指针走两步是一定会相遇的。因为快指针比慢指针快一步，假设快指针需要N步追上慢指针，一次追一步根本不会错过。
图5-2 快指针追慢指针1
5.2.1. 步数改变呢？
如果快指针一次走3步那么也一定会遇到吗？
答案是不一定，分析如下：
首先，快指针与慢指针的步差为2。那么实际问题就可以被简化为在一个圆环里，单个指针要到达距离N个位置的节点，但是由于一次走两步，所以当N为奇数的时候会在第一圈的时候错过该位置。第一圈已经到不来指定节点了，那么第2圈以后呢？
第二圈以后到达指定节点的距离为n*C+N，也就是说如果步差能够将距离整除那么之后就还是能遇到，回到假设的情况。如果C为偶数，偶数乘以一个数加上一个奇数仍然是奇数，那么奇数永远都不会被2整除，这样每次都会错过慢指针。所以如果改变步差是可能会导致快慢指针遇不到的。
5.3. 解题代码
根据解题思路，代码如下：
bool hasCycle(struct ListNode *head) {
struct ListNode* quick = head;
struct ListNode* slow = head;
//快慢指针遍历所有节点
while(quick && quick->next)
{
quick = quick->next->next;
slow = slow->next;
//两指针相遇，说明一定有环
if(quick == slow)
{
return true;
}
}
//遍历完成说明没有环
return false;
}运行结果如下，代码很简捷：
6. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL OJ链接
6.1. 题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
6.2. 题解思路
这一题相当于是练习题5的进阶，首先需要确认链表带坏，这部分的思路和代码直接沿用。问题就是怎么确认入环节点了。
图6-1 图示
首先快指针比慢指针每次移动都快一步，假设移动了 t 次。
那么快指针的移动总步数为 2 * t 步， 慢指针移动步数为 t 步。
因为快指针会追上慢指针，所以快指针和慢指针之间的步差应该为 n * C ，其中 n 表示转的圈数。为什么步差为 n * C 呢？因为，快指针会比慢指针多绕 n 圈最后追上慢指针。
也就是说 2*t - t = n * C -> t = n * C。
那么慢指针的步数可视化之后会如下图所示：
图6-2
转换一下思路， n * C 还能等于什么。
图6-3
如图6-3所示，n * C 还相当于转了n圈。
好巧不巧，如果这个圈数再加上一个 L 那么 n * C + L就相当于从链表头结点开始进入环，然后转了 n 圈回到了环开头。
回到快慢指针相遇得到情况，我们只需要从相遇节点开始再走上 L 步就能到入环结点。
6.3. 解题代码
根据解题思路代码如下：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* quick = head;
struct ListNode* slow = head;
//快慢指针遍历所有节点
while(quick && quick->next)
{
quick = quick->next->next;
slow = slow->next;
//两指针相遇，说明一定有环
if(quick == slow)
{
//有环找第一个入环节点
struct ListNode* meet = slow;
slow = head;
//相遇节点走上链表未成环部分长度刚好到入环第一个节点
while(1)
{
if(slow == meet)
{
//遇到了返回节点
return meet;
}
else
{
//没遇到就继续遍历
slow = slow->next;
meet = meet->next;
}
}
}
}
//遍历完成说明没有环
return NULL;
}根据解题思路，在循环while（1）中一定能够遇到。所以这么写也可以。
那么结果如下：
作者结语
多的就不说了，链表是真的好玩好吧。
