题目:给定一个链表的头节点 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;
}
题目:给定一个单链表 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;
}