一、环形链表Ⅰ
1、题目描述
https://leetcode.cn/problems/linked-list-cycle
2、算法分析
思路：快慢指针
根据上图所示的流程，我们可以推测出这样一个结论：若链表带环，快慢指针一定会相遇。
那么，这个猜测是否正确呢？下面给出严格的证明——
证明1：在环形链表中，快慢指针为什么在环里一定会相遇？（慢指针每次走一步，快指针每次走两步）
以上面的图为例，假设slow刚入环，此时slow和fast之间的距离达到最大，最大值为N。接下来，slow前进一步，fast前进两步，此时两者距离变为N-1。同理，fast和slow再继续向后走，距离依次变为N-2，N-3……2，1，0 。当距离为0时，两指针相遇。
证明2：在环形链表中，慢指针每次走一步，但快指针每次走3/4/5/6……步，快慢指针在环里是否还会相遇？
假设慢指针每次走一步，快指针每次走三步。还是以刚才那副图为例，fast和slow之间的距离依次变为N-2，N-4，……如果N为偶数，那么最后距离变为4,2,0，快慢指针相遇。但是N为奇数的话，最后距离变为3,1，-1，距离变为-1时说明出现了套圈，也就是二者并没有相遇，此时二者之间的距离为C-1（假设环的周长为C）。那下一圈二者能否相遇呢？根据刚才的分析，当N为奇数的时候才会出现套圈的情况，若C-1为奇数，即C为偶数，一定不会相遇。若C-1为偶数，即C为奇数，下一圈一定会相遇。快指针走的总路程是慢指针的三倍，也就是3 * 慢指针 = 快指针。我们假设慢指针刚入环，快指针已经走了n圈，也就是慢指针当前走的总路程为L，快指针走的总路程为L+C-N+nC。带入公式得：3L = L + C - N + nC。化简得：2L = (n+1)C - N。等式左边的2L一定是偶数，根据数学知识可以知道：①偶数 - 偶数 = 偶数 ②奇数 - 奇数 = 偶数。所以我们得到下面的结论：C为奇数，N为奇数；C为偶数，N为偶数。但是我们先前又得到N为奇数，C为奇数一定会相遇；N为奇数，C为偶数一定不会相遇。所以C为偶数，N为奇数的情况不存在，既然不存在该情况，也就是说快指针一次走三步，最终也一定会相遇。同理，快指针每次走4、5、……步也是一样的道理。综上：快指针无论每次走多少步，快慢指针都可以在带环链表中相遇。但是在编写代码时会有额外程序步骤的引入，所以我们习惯上还是快指针走两步，慢指针走一步~
3、参考代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{
//快慢指针
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
//相遇
return true;
}
}
return false;
}二、环形链表Ⅱ
1、题目描述
https://leetcode.cn/problems/linked-list-cycle-ii
2、算法分析
思路：快慢指针
slow和fast相遇节点距离入环节点的距离为1，而头结点距离入环节点的距离也是1~
slow和fast相遇节点距离入环节点的距离为0，而头结点距离入环节点的距离也是0~
slow和fast相遇节点距离入环节点的距离为2，而头结点距离入环节点的距离也是2~
根据上面三个案例，我们可以作出猜想：快慢指针相遇点和头结点到入环起始节点的距离是相等的。下面给出严格的证明——
证明：为什么在带环链表中，快慢指针相遇点和头结点到入环第一个结点的距离相等？
快指针走的总路程是慢指针的两倍， 根据这句话，我们得到公式：2 * slow = fast。慢指针走过的总路程为L + X，快指针走过的总路程为L + X + nR。带入上述公式得：2(L + X) = L + X + nR。化简得：L + X = nR。即L = nR - X。变形一下得：L = (n-1)R + (R-X)。L是头结点到入环第一个结点的距离，R - X是相遇点到入环第一个结点的距离，(n-1)R是走过的完整的环的路程，对师资并没有影响，所以得到L = R - X，也就是快慢指针相遇点和头结点到入环第一个结点的距离相等。证明完毕~
3、参考代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{
//快慢指针
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(fast == slow)
{
//找相遇点
//相遇点和头结点到入环第一个节点的距离相等
ListNode* pcur = head;
while(pcur != slow)
{
slow = slow->next;
pcur = pcur->next;
}
//pcur == slow
return pcur;
}
}
return NULL;
}三、链表分割
1、题目描述
2、算法分析
思路：创建两个链表（小链表、大链表），遍历原链表，小的结点尾插到小链表中，大的节点尾插到大链表中，最后让大链表和小链表首尾相连。
3、参考代码
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition
{
public:
ListNode* partition(ListNode* pHead, int x)
{
//创建两个带头的空链表
ListNode* lessHead, *lessTail;
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* greaterHead, *greaterTail;
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* pcur = pHead;
while(pcur)
{
if(pcur->val < x)
{
lessTail->next = pcur;
lessTail = lessTail->next;
}
else
{
greaterTail->next = pcur;
greaterTail = greaterTail->next;
}
pcur = pcur->next;
}
//大链表尾结点的next指针置为NULL(避免死循环)
greaterTail->next = NULL;
//大小链表首尾相连
lessTail->next = greaterHead->next;
ListNode* ret = lessHead->next;
free(lessHead);
free(greaterHead);
lessHead = greaterHead = NULL;
return ret;
}
};