七、链表的回文结构
题目链接
题目链接（来源：牛客网）
题目描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
解题思路
根据回文链表的结构，我们找到链表的终点，然后逆置后半段链表，与前半段比较，如果重合的话，证明原链表就是回文链表，否则就不是回文链表，为了严谨，最后我们应该把原链表还原。
代码实现
class PalindromeList { public: struct ListNode* reverseList(struct ListNode* head){//逆置链表 struct ListNode* newhead = NULL; struct ListNode* next = NULL; struct ListNode* cur = head; while(cur) { next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; } struct ListNode* middleNode(struct ListNode* head){//找到中间结点 struct ListNode* slow, *fast; fast = slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } bool chkPalindrome(ListNode* A) { // write code here struct ListNode* mid = middleNode(A);//找到中间节点 struct ListNode* r_mid = reverseList(mid);//逆置链表后半部分 while(A && r_mid) { if(A->val != r_mid->val) return false; A = A->next; r_mid = r_mid->next; } return true; } };
八、相交链表
题目链接
160.相交链表 - 力扣（LeetCode）
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。这两个链表不相交，因此返回 null 。
解题思路
根据相交链表的结构性质，我们可以知道，如果两个链表相交，那么最坏的可能就是两个链表只有最后一个节点是相交的，也就是“同一个”节点，而且我们不知道两个链表在相交之前分别由多少个节点，那么可以通过比较两个链表的长度来算，链表长度之差就是长链表在相交节点之前比锻炼表多的节点个数。然后让长链表先走相差个数步，然后两个链表同时走，每走一步比较一下节点是否相同，直到节点相同跳出循环，或者任意一个链表结束结束循环返回空指针。
代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA == NULL || headB == NULL) return NULL; struct ListNode* curA = headA, *curB = headB; int lenA = 1, lenB = 1; while(curA->next)//遍历链表，找尾结点，记录链表长度 { curA = curA->next; ++lenA; } while(curB->next) { curB = curB->next; ++lenB; } if(curA != curB)//判断是否相交 return NULL; struct ListNode* longList = headA, *shortList = headB; if(lenA < lenB) { longList = headB; shortList = headA; } //长的链表先走差距步 int gap = abs(lenA-lenB); while(gap--) { longList = longList->next; } while(longList != shortList) { longList = longList->next; shortList = shortList->next; } return longList; }
九、环形链表
题目链接
141.环形链表 - 力扣（LeetCode）
题目描述
给你一个链表的头节点 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
解释：链表中没有环。
解题思路
定义快慢指针，快指针一次走两步，慢指针一次走一步，如果链表有环，当快慢指针都进环以后，快指针会追逐慢指针，直到两个指针相遇，return true，否则快指针先遍历完节点，结束循环，return false。
代码实现
bool hasCycle(struct ListNode *head) { struct ListNode* slow,*fast; slow = fast = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(fast == slow) return true; } return false; }
十、环形链表2
题目链接
142.环形链表 2 - 力扣（LeetCode）
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
解题思路
思路一：
L表示进环之前的长度，C表示环的长度，所以慢指针走的长度是L+X，假设快指针在环内绕了n圈以后与慢指针相遇，所以快指针走的长度是L+nC+x，由于快指针的速度是慢指针的二倍，所以2*(L+X) = L+nC+X，化简得：L = nC-X，所以一个指针从相遇点开始走，另一个指针从链表头开始走，两个指针会在进环点相遇。所以当两个指针相遇时，return该指针即可。
代码实现
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow,*fast; fast = slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(fast == slow) { struct ListNode* meet = fast; struct ListNode* cur = head; while(cur != meet) { cur = cur->next; meet = meet->next; } return meet; } } return NULL; }
思路二：
可以把相遇点和原来的头看成是两个链表的的头，然后进环点看成是两个链表的相交点，找到相交点返回即可。找相交链表的相交点的问题在上面我们已经实现过了。但是由于原链表有环，所以应该把相遇点meet的next置空，在实现操作之后恢复链表。
代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA == NULL || headB == NULL) return NULL; struct ListNode* curA = headA, *curB = headB; int lenA = 1, lenB = 1; while(curA->next)//遍历链表，找尾结点 { curA = curA->next; ++lenA; } while(curB->next) { curB = curB->next; ++lenB; } if(curA != curB)//判断是否相交 return NULL; struct ListNode* longList = headA, *shortList = headB; if(lenA < lenB) { longList = headB; shortList = headA; } //长的链表先走差距步 int gap = abs(lenA-lenB); while(gap--) { longList = longList->next; } while(longList != shortList) { longList = longList->next; shortList = shortList->next; } return longList; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow,*fast; fast = slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(fast == slow) { struct ListNode* meet = slow; struct ListNode* next = meet->next; meet->next = NULL; struct ListNode* entryNode = getIntersectionNode(head,next); meet->next = next; return entryNode; } } 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：
输入：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]]
解题思路
在拷贝节点的时候，对于val，直接复制即可，但是其中的指针不能够直接复制，因为指针存放的是节点的地址，拷贝的新节点和原节点的地址是不同的。在这里拷贝的时候我们应该遍历链表，每遇到一个节点，就应该拷贝一次，并且将拷贝的节点链接在原节点的后面，然后再给random赋值为原节点的next，再将拷贝节点取下来重新链接成为新节点并且恢复原链表。
代码实现
struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; struct Node* copy = NULL; struct Node* next = NULL; //复制节点，链接在原节点的后面 while(cur) { //复制链接 next = cur->next; copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; cur->next = copy; copy->next = next; //迭代 cur = next; } //更新random cur = head; while(cur) { copy = cur->next; if(cur->random == NULL) copy->random = NULL; else copy->random = cur->random->next; cur = cur->next->next; } //解下来copy节点，回复原链表 cur = head; struct Node* copyHead; struct Node* copyTail; copyHead = copyTail = NULL; while(cur) { copy = cur->next; next = copy->next; //取节点尾插 if(copyTail == NULL) copyHead = copyTail = copy; else { copyTail->next = copy; copyTail = copyTail->next; } //恢复原链接 cur->next = next; //迭代器 cur = next; } return copyHead; }
