【Leetcode -142.环形链表Ⅱ -143.重排链表】
【Leetcode -142.环形链表Ⅱ -143.重排链表】
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;
}腾讯云开发者
