Leetcode -142.环形链表Ⅱ
题目：给定一个链表的头节点 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
解释：链表中没有环。
我们的思路是，如下图，a为没进入环的长度，即环的外部，b+c则是环的长度，b是slow进入环之后，与fast相遇前走的长度；假设fast与slow相遇时，fast已经在环内走了n圈，则fast走的路程为：n*(b+c)+a+b；又因为fast每次走两步，slow每次走一步，所以fast = 2slow，而在相遇时slow走的路程是：a+b；所以有 ：n * (b+c) + a + b = 2 * (a+b)， 化简后得：a = n * (b+c) - b，可以理解为 n 圈减去 b 的长度，即为 c 的长度，所以a = c；所以我们可以在fast与slow相遇时定义一个ptr指针从头开始走，它和slow每次走一步，直到它们相遇，相遇的位置即是进入环的位置；
struct ListNode* detectCycle(struct ListNode* head) { //fast和slow从head开始走，slow每次走一步，fast每次走两步 struct ListNode* slow = head, * fast = head; //fast，fast->next，fast->next->next任一为空，循环结束 while (fast && fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; //当slow和fast相遇 if (slow == fast) { //定义ptr指针，它与slow每次走一步，直到相遇，就是开始进入环的位置 struct ListNode* ptr = head; while (ptr != slow) { ptr = ptr->next; slow = slow->next; } return ptr; } } //其他情况返回空 return NULL; }
Leetcode - 143.重排链表
题目：给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1, 2, 3, 4]
输出：[1, 4, 2, 3]
示例 2：
输入：head = [1, 2, 3, 4, 5]
输出：[1, 5, 2, 4, 3]
我们的思路是，将找到原链表的中间节点，分为两部分，然后反转中间节点之后的部分，再将前面部分与反转后的后部分的链表合并在一起即可；
//找到中间节点 struct ListNode* Findmid(struct ListNode* head) { struct ListNode* fast = head, * slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } //反转后半部分的链表 struct ListNode* Reverse(struct ListNode* head) { struct ListNode* prev = NULL, * cur = head; while (cur) { struct ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } //合并链表 void Combine(struct ListNode* head, struct ListNode* reverse) { struct ListNode* cur = head, * ptr = reverse, * next = cur->next, * ptrnext = ptr->next; while (ptrnext) { cur->next = ptr; ptr->next = next; ptr = ptrnext; cur = next; next = next->next; ptrnext = ptrnext->next; } } void reorderList(struct ListNode* head) { if (!head) return head; //找到中间链表的节点，反转，合并即可 struct ListNode* mid = Findmid(head); struct ListNode* reverse = Reverse(mid); Combine(head, reverse); return head; }
