七、回文链表
题目链接
剑指 Offer II 027. 回文链表 - 力扣（LeetCode）
题目描述
给定一个链表的 头节点head **，**请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
思路分析
思路
找到链表的中间节点，将链表中间及以后的节点反转，然后用两个指针，一个指向链表开头，另一个指向反转部分的开头，遍历观察二者的val是否相等。时间复杂度：O(N) 空间复杂度：O(1)
易错点
我们反转的是中间及以后的节点，但是并未改变中间节点的前一个节点的next；也就是说，中间节点的前一个节点指向的是反转后的链表的最后一个节点；所以不管是链表长度是奇数还是偶数，我们都可以直接判断指针指向节点的val是否相等。
代码实现
//链表的中间节点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast, *slow; slow = fast = head; //注意：while条件中fast一定要写前面，不然偶数个时fast->next会造成空指针解引用 while(fast && fast->next) //节点是奇数还是偶数未知注意： { slow = slow->next; fast = fast->next->next; } return slow; } //反转链表 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; } //将链表的中间及以后的节点逆置，用两个指针分别指向头节点和中间节点，然后遍历链表看指针指向的节点的val是否相等 bool isPalindrome(struct ListNode* head){ //找到链表的中间节点 struct ListNode* mid = middleNode(head); //从链表的中间节点开始翻转链表 struct ListNode* reverse_mid = reverseList(mid); //遍历链表，看元素是否相等 struct ListNode* cur = head; while(cur && reverse_mid) { if(cur->val != reverse_mid->val) return false; cur = cur->next; reverse_mid = reverse_mid->next; } return true; //循环结束还没返回说明是回文链表 }
八、相交链表
题目链接
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路分析
从上面的例图我们可以知道：相交链表从相交的节点开始，后面的节点都是相同的，即相交链表的尾结点一定是相同的；所以我们可以先求出两个链表的长度，让较长的链表先走差距步；然后遍历两个链表，两个链表的节点地址相同处就是相交的起始节点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
由于两个链表的长度不一定是相同的，所以我们不能直接对比两个链表的节点地址，这样会发生错位，而是应该先让两个链表对齐。
代码实现
//先让长度较长的链表向后走n步，让两个链表相等；然后开始遍历两个链表，找出地址相同的第一个节点，就是相交的起始节点 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA, *curB = headB; int lenA = 1; int lenB = 1; if(curA == NULL || curB == NULL) //如果两个链表中有一个为空直接返回空 return NULL; //求出两个节点的长度 while(curA->next) { lenA++; curA = curA->next; } while(curB->next) { lenB++; curB = curB->next; } if(curA != curB) return NULL; //如果两个链表的尾结点的地址不同，则一定不相交；否则，就一定相交 //让长度较长的链表先走差距步 curA = headA; curB = headB; int k = abs(lenA - lenB); if(lenA > lenB) { while(k--) { curA = curA->next; } } else { while(k--) { curB = curB->next; } } //从cur位置处往后遍历链表，第一个相同地址的节点就是相交的起始节点 while(curA && curB) { if(curA == curB) return curA; curA = curA->next; curB = curB->next; } return NULL; //不加LeetCode不给过，但实际上不用加 }
九、环形链表
题目链接
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
思路分析
快慢指针：定义两个指针 – fast 和 slow，快指针一次走两步，慢指针一次走一步，如果链表带环，二者最终会在链表的某个节点相遇。时间复杂度：O(N) 空间复杂度：O(1)
代码实现
//快慢指针：定义两个指针--fast和slow，fast一次走两步，slow一次走一步，如果链表有环，slow和fast最终会相等 bool hasCycle(struct ListNode *head) { struct ListNode* fast = head, *slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(fast == slow) //如果快指针与慢指针相遇就代表有环 return true; } return false; //如果循环可以结束就代表没环 }
面试题（重点）
上面的代码十分简单，难点在于下面这几个面试题：
1、为什么快指针每次走两步，慢指针每次走一步，二者最终一定会在环中相遇？
2、快指针一次走三步，慢指针一次走一步，可不可以？
3、快指针一次走X步，慢指针一次走Y步可不可以？
实现我们先来解答第一个问题：
快指针每次走两步，慢指针每次走一步，所以当慢指针走到链表的中间节点时快指针刚好入环；
当慢指针入环时，快指针至少已经在环中走了一圈了：当链表的环比较大时，快指针可能只走了一圈多几步（最大的情况是链表的尾结点刚好链接到链表的头节点，此情况二者在头结点处相遇）；当链表的环比较小时，快指针可能在环中走了很多圈（最小的情况是链表的尾结点连接到尾结点，此情况二者在尾结点处相遇）；
总之：当慢指针入环时，慢指针和快指针直接的距离最小为0，最大为C-1（快指针在慢指针的前一个/后一个节点），其中C为环的长度；
而快指针一次走两步，慢指针一次走一步，二者之间的距离一次缩小1，所以快指针最坏走C-1步就能追上慢指针，二者相遇；所以快指针每次走两步，慢指针每次走一步，二者最终一定会在环中相遇。
然后我们来解答第二个问题：
有了上面的基础，后面的两个问题就比较简单了：快指针一次走三步，慢指针一次走两步，所以当慢指针走到链表的1/3处时快指针，入环；当慢指针入环时，快指针在环中走了k圈多n步（n步即是二者之间的距离）；
现在两个指针之间的距离为N，快指针一次走三步，慢指针一次走两步，二者之间的距离一次缩小2；所以这里就有两种情况：1、二者之间相差的步数n为偶数，这种情况下快指针在一圈内一定能够追上慢指针；
2、二者之间相差的步数n为奇数，这种情况下快指针和慢指针最后会相差一步，然后再往后走，快指针就会直接超过慢指针，而不会与慢指针相遇，这时候慢指针与快指针的距离又变为了C-1；这时又需要看环的长度，如果环的长度C为奇数，那么C-1为偶数，二者在这一圈内会相遇；如果C为偶数，那么C-1为奇数，二者就永远不会相遇了；
所以，当快指针一次走三步，慢指针一次走两步时，二者可能在环中相遇，也可能永远都不会相遇。
最后我们来总结第三个问题：
在解决了上面两个问题之后，第三问题的答案也就呼之欲出了：快指针一次走X步，慢指针一次走Y步，慢指针入环时二者的距离为N，快指针与慢指针之间的距离一次缩小X-Y，如果X-Y为1，则一定能够相遇；如果X-Y大于1，如2,3,4… … 可能相遇，也可能不相遇。
十、环形链表 II
题目链接
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路分析
思路1
结论法：定义两个指针 – fast 和 slow，快指针一次走两步，慢指针一次走一步，首先求出二者在环中的相遇点；然后一个指针从链表的头开始走，另一个指针从相遇点开始走，最终二者会在入环点相遇。时间复杂度：O(N) 空间复杂度：O(1)
结论证明：我们假设环的长度为C，环之前的节点的长度为L，慢指针与快指针在环中X距离处相遇，相遇时快指针已经在环中走了N圈；则如下图所示：
代码实现
//法一：公式结论法--一个指针从链表的头开始走，另一个指针从相遇点开始走，二者最终会在入环点相遇 struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast = head, *slow = head, *cur = head; while(fast && fast->next) { //迭代 slow = slow->next; fast = fast->next->next; //找到相遇的节点 if(fast == slow) { struct ListNode* meet = slow; //一个指针从头开始走，另一个指针从相遇点开始走 while(cur != meet) { cur = cur->next; meet = meet->next; } return cur; //二者最终会在入环点相遇 } } return NULL; //无环 }
思路2
将链表求环问题转化为链表相交问题：定义两个指针 – fast 和 slow，快指针一次走两步，慢指针一次走一步，首先求出二者在环中的相遇点；然后记录下相遇点的下一个节点并让相遇点的next指向NULL；让相遇点的下一个节点作为新链表的头，与原链表求交点；最后再把相遇点的next复原。时间复杂度：O(N^2) 空间复杂度：O(1)
易错点
1、我们需要将相遇点的next置空，否则在求两个链表的交点的时候会发生死循环；
2、由于题目要求不修改原链表，所以最后我们需要把相遇点的next复原；
代码实现
//求两个链表的交点 //先让长度较长的链表向后走n步，让两个链表相等；然后开始遍历两个链表，找出地址相同的第一个节点，就是相交的起始节点 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA, *curB = headB; int lenA = 1; int lenB = 1; if(curA == NULL || curB == NULL) //如果两个链表中有一个为空直接返回空 return NULL; //求出两个节点的长度 while(curA->next) { lenA++; curA = curA->next; } while(curB->next) { lenB++; curB = curB->next; } if(curA != curB) return NULL; //如果两个链表的尾结点的地址不同，则一定不相交；否则，就一定相交 //让长度较长的链表先走差距步 curA = headA; curB = headB; int k = abs(lenA - lenB); if(lenA > lenB) { while(k--) { curA = curA->next; } } else { while(k--) { curB = curB->next; } } //从cur位置处往后遍历链表，第一个相同地址的节点就是相交的起始节点 while(curA && curB) { if(curA == curB) return curA; curA = curA->next; curB = curB->next; } return NULL; //不加LeetCode不给过，但实际上不用加 } //法二：转换法--把环的入口问题转换为环的相交问题，即把链表从相遇点断开，一个指针从头开始走，一个指针从相遇点后面一个节点开始走，求二者相交 struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head, *fast = head, *cur = head; while(fast && fast->next) { //迭代 slow = slow->next; fast = fast->next->next; //找到相遇点 if(slow == fast) { //记录相遇点的下一个节点，并把链表从相遇点断开，避免求相交的时候发生死循环 struct ListNode* meet = fast; struct ListNode* next = meet->next; meet->next = NULL; //求两个链表相交 struct ListNode* intersection = getIntersectionNode(cur, next); return intersection; //恢复原链表 meet->next = next; } } return NULL; //无环 }
十一、复制带随机指针的链表
题目链接
138. 复制带随机指针的链表 - 力扣（LeetCode）
题目描述
给你一个长度为 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
暴力求解：1、拷贝原链表的每个节点；2、得到原链表中每个节点的random指针指向的节点在链表中的相对位置；3、让新链表中每个节点的random指针指向处于相对位置的节点。时间复杂度：O(N^2) 空间复杂度：O(N)
代码实现
//拷贝节点 struct Node* CopyNode(struct Node* cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->next = NULL; copy->val = cur->val; copy->random = NULL; return copy; } //法一：1、拷贝原链表的每个节点；2、得到原链表中每个节点的random指针指向的节点在链表中的相对位置；3、让新链表中每个节点的random指针指向处于相对位置的节点 struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; struct Node* newhead = NULL, *tail = NULL, *copy = NULL; //拷贝节点 while(cur) { //如果是复制第一个节点，需要改变头 if(tail == NULL) { copy = CopyNode(cur); newhead = tail = copy; } else { copy = CopyNode(cur); tail->next = copy; tail = tail->next; } //迭代 cur = cur->next; } //得到原链表中每个节点的random指针指向的节点在链表中的相对位置；并让新链表中每个节点的random指针指向处于相对位置的节点 cur = head; struct Node* copycur = newhead; while(cur && copycur) { int count = 0; struct Node* cur1 = head; //找到cur节点的random指针指向的节点在链表中的相对位置 while(cur->random != cur1) { count++; cur1 = cur1->next; } struct Node* copycur1 = newhead; //让copycur中每个节点的random指针指向处于相对位置的节点 while(count--) { copycur1 = copycur1->next; } copycur->random = copycur1; //迭代 cur = cur->next; copycur = copycur->next; } return newhead; }
思路2
1、将所有拷贝的节点链接到原节点的后面；2、将原节点的random指针指向节点的下一个节点赋给拷贝节点的random；3、将拷贝节点从原链表中分离出来，尾插到新链表中，并修复原链表中各节点的链接关系。时间复杂度：O(N) 空间复杂度：O(N)
易错点
1、由于我们是直接把拷贝节点链接到了原节点的后面，所以我们一定要注意链接关系的正确修改；并且迭代的时候我们需要让cur指向拷贝节点的下一个节点，即copy->next，而不是指向原节点的下一个节点，即cur->next；
2、在法一中，当原节点的random为NULL时，寻找相对位置的while循环会一直执行，直到cur1走到链表尾结点的下一个节点(NULL)，此时count为链表长度+1；然后新链表会把count处节点的地址(NULL)赋给对应节点的random，此时逻辑是正常的；
但是在法二中，当我们节点的random为NULL时，cur->random->next就会造成空指针解引用问题，所以这里我们需要对random为空的情况单独处理，需要特别注意，非常容易错；
3、由于我们在拷贝节点的时候就已经让尾结点的拷贝节点的next指向尾结点的next (NULL) 了，所以我们将拷贝节点插入到新链表中时不用特意将最后一个拷贝节点的next置空。
代码实现
//拷贝节点 struct Node* CopyNode(struct Node* cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->next = NULL; copy->val = cur->val; copy->random = NULL; return copy; } //法二：1、将所有拷贝的节点链接到原节点的后面；2、将原节点的random指针指向节点的下一个节点赋给拷贝节点的random；3、将拷贝节点从原链表中分离出来，尾插到新链表中，并修复原链表中各节点的链接关系 struct Node* copyRandomList(struct Node* head) { struct Node* cur = head, *copy = NULL, *next = NULL; struct Node* newhead = NULL, *tail = NULL; //1、将所有拷贝的节点链接到原节点的后面 while(cur) { //拷贝节点、修改链接关系 copy = CopyNode(cur); next = cur->next; cur->next = copy; copy->next = next; //迭代 cur = copy->next; } //2、将原节点的random指针指向节点的下一个节点赋给拷贝节点的random； cur = head; while(cur) { copy = cur->next; //原节点的random指针指向节点的下一个节点就是copy的random需要指向的节点 //这里需要判断cur的randon是否为空，为空就不能进行random->next操作 if(cur->random == NULL) copy->random = NULL; else { copy->random = cur->random->next; cur = copy->next; } //迭代 cur = copy->next; } //3、将拷贝节点从原链表中分离出来，尾插到新链表中，并修复原链表中各节点的链接关系 cur = head; while(cur) { copy = cur->next; //尾插第一个节点时，需要改变头 if(tail == NULL) { newhead = tail = copy; cur->next = copy->next; //修复原链表的链接关系 } else { tail->next = copy; tail = tail->next; cur->next = copy->next; } //迭代 cur = copy->next; } return newhead; }
