🐱作者：傻响
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！
目录
🙉【LeetCode】[17.04]. 消失的数字
题目链接：面试题 17.04. 消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：[3,0,1] 输出：2示例 2：
输入：[9,6,4,2,3,5,7,0,1] 输出：8
🙊第一种解题方法：《排序》
// 第一种方式：排序的方式（时间都原因无法通过）
int missingNumber(int* nums, int numsSize)
{
// 排序
for (int i = 0; i < numsSize - 1; i++)
{
for (int j = 0; j < numsSize - 1 - i; j++)
{
if (nums[j] > nums[j + 1])
{
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
// 寻找数组中数字加1的对数
for (int i = 0; i < numsSize; i++)
{
if (nums[i] + 1 != nums[i + 1])
return nums[i]+1;
}
return -1;
}🙊第一种解题方法：《相减法》
将0~N个数组加到一起结果是：result1。 在把数组中数的数加到一起结果是：result2。 result1-result2 就是我们要找到的数。
// 第二种方式：相减法（时间都原因无法通过）
int missingNumber2(int* nums, int numsSize)
{
int result1 = 0, result2 = 0;
// 将0~N个数组加到一起结果是
for (int i = 0; i < numsSize + 1; i++)
{
result1 += i;
}
// 在把数组中数的数加到一起结果是
for (int i = 0; i < numsSize; i++)
{
result2 += nums[i];
}
// 属于的值就是缺少的那个数值。
return result1 - result2;
}🙊第三种解题方法：《异或法》
异或的方式。
先与数组中的数值进行异或。
在与数组中0~N进行异或。
int missingNumber3(int* nums, int numsSize)
{
int x = 0;
// 在本数组中进行异或。
for (int i = 0; i < numsSize; i++)
{
x ^= nums[i];
}
// 在和0~N所有的数进行异或
for (int i = 0; i < numsSize + 1; i++)
{
x ^= i;
}
return x;
}🙉【LeetCode】[17.04]. 消失的数字
题目链接：189. 轮转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
void Reverse(int* nums, int begin, int end)
{
while (begin < end)
{
int temp = *(nums + begin);
*(nums + begin) = *(nums + end);
*(nums + end) = temp;
begin++;
end--;
}
}
void Rotate(int* nums, int numsSize, int k)
{
if (k >= numsSize)
{
k %= numsSize;
}
// 左旋转
///Reverse(nums, 0, numsSize - 1 - k);
//Reverse(nums, numsSize - k, numsSize - 1);
//Reverse(nums, 0, numsSize - 1);
// 右旋转
Reverse(nums, 0, k - 1);
Reverse(nums, k, numsSize - 1);
Reverse(nums, 0, numsSize - 1);
}🙉【LeetCode】[27]. 移除元素
描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
实例1：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。实例2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
题目解析：
标准代码：
int removeElement(int* nums, int numsSize, int val)
{
// 定义一个来源和目标。
int source = 0, destination = 0;
// 遍历整个数组，长度小于numsSize
while(source < numsSize)
{
// 如果元素的值和val不相等(那就不是要删除的值)，那就拿这个值拿到destination指向的数组位置上。
if(nums[source] != val)
{
*(nums + destination) = *(nums + source);
++source;
++destination;
}
else // 如果是的话就不让destination指向的数组位置上放，source继续向前走。
{
++source;
}
}
return destination;
}🙉【LeetCode】[26].删除有序数组中的重复项
题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）
描述：
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
实例1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。实例2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums已按 升序 排列
题目解析：
标准代码：
int removeDuplicates(int* nums, int numsSize)
{
// 定义一个来源和目标。
int source = 0, destination = 0;
// 遍历整个数组，长度小于numsSize
while(source < numsSize)
{
// 如果source指向数组的位置和destination指向数组的位置值是一样的，说明是重复的source前进。
if(nums[source] == nums[destination])
{
++source;
}
else// 如果source指向数组的位置和destination指向数组的位置值不是一样的，
{ // 让destination先++ 这样destination就移动了下一个位置，让source复制。
nums[++destination] = nums[source++];
}
}
// destination永远少移动一下，所以返回的是后加1.
return destination + 1;
}🙉【LeetCode】[88]. 合并两个有序数组
题目链接：88. 合并两个有序数组 - 力扣（LeetCode）
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
实例1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。实例2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。实例3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
题目解析：
标准代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
// 定义指针的位置。
int end = m + n - 1;
int end1 = m - 1, end2 = n - 1;
// 遍历整个数组，两个指针都不小于0
while(end1 >= 0 && end2 >= 0)
{
// 数组nums1的end1指向的元素大于nems2的end2指向的元素，将nums2的值传递给nums1的end指向的元素。
if(nums1[end1] > nums2[end2])
{
nums1[end--] = nums1[end1--];
}
else // 相反
{
nums1[end--] = nums2[end2--];
}
}
// 程序走到这里总有一组数据传递完成。
// 如果end2对应的nums2数组传递完成了，那么就不需要进行处理了。
// 如果end1对应的num1数组传递完成了，那么这时候需要进行处理把nums2剩余的值继续传递完成。
while(end2 >= 0)
{
nums1[end--] = nums2[end2--];
}
}🙉【LeetCode】[203].移除链表元素
题目链接：203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
实例1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]示例 2：
输入：head = [], val = 1 输出：[]示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
🙊第一种解题方式：《双指针》
// 第一种方式
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode *pCurrent = head, *pPrev = NULL;
// pCurrent == NULL 代表链表遍历完了。
while(pCurrent != NULL)
{
// 1、节点值和val值不相等。
// 2、节点值与val值相等。
if(pCurrent->val != val)
{
pPrev = pCurrent;
pCurrent = pCurrent->next;
}
else
{
// 1、非头删除
// 2、头删除
if(pCurrent != head)
{
pPrev->next = pCurrent->next;
free(pCurrent);
pCurrent = pPrev->next;
}
else
{
head = head->next;
free(pCurrent);
pCurrent = head;
}
}
}
// 返回新的头节点
return head;
}🙊第二种解题方式：《将不是val的值尾插到新链表》
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* pCurrent = head;
struct ListNode* newNode = NULL;
struct ListNode* pTail = NULL;
while (pCurrent != NULL)
{
// pCurrent-val = val / pCurrent-val != val 两种情况。
if (pCurrent->val != val)
{
// 等于空的话创建新的节点。
if (pTail == NULL)
{
newNode = pTail = pCurrent;
}
else
{
pTail->next = pCurrent;
pTail = pTail->next;
}
pCurrent = pCurrent->next;
}
else
{
struct ListNode* del = pCurrent;
pCurrent = pCurrent->next;
free(del);
del = NULL;
}
}
if (pTail != NULL)
pTail->next = NULL;
// 返回新的头节点。
return newNode;
}🙊第三种解题方式：《带哨兵头》
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* pCurrent = head;
// 定义哨兵头
struct ListNode* pGuardHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* pTail = pGuardHead;
while(pCurrent != NULL)
{
//1、pCurrent->val == val
//2、pCurrent->val != val
if(pCurrent->val != val)
{
// 哨兵下一个节点指向pCurrent
pTail->next = pCurrent;
// 两个节点都进行下移动
pTail = pTail->next;
pCurrent = pCurrent->next;
}
else
{
struct ListNode* del = pCurrent;
pCurrent = pCurrent->next;
free(del);
del = NULL;
}
}
if(pTail != NULL)
pTail->next = NULL;
// 返还头节点，将哨兵位释放掉。
head = pGuardHead->next;
free(pGuardHead);
pGuardHead = NULL;
return head;
}🙉【LeetCode】[21].合并两个有序链表
题目链接：21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 2：
输入：l1 = [], l2 = [] 输出：[]示例 3：
输入：l1 = [], l2 = [0] 输出：[0]提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
// 创建哨兵位节点。
struct ListNode* pGuardHead = (struct ListNode*)malloc(sizeof(struct ListNode));
if(pGuardHead == NULL)
{
perror("mergeTwoLists malloc fail!\n");
exit(-1);
}
else
{
pGuardHead->next = NULL;
}
struct ListNode* pTail = pGuardHead;
// 两个链表的当前指针。
struct ListNode* pCurrent1 = list1;
struct ListNode* pCurrent2 = list2;
while(pCurrent1 != NULL && pCurrent2 != NULL)
{
// 比较两个节点那个节点内容小，小的放入新的节点上
if(pCurrent1->val < pCurrent2->val)
{
pTail->next = pCurrent1;
pCurrent1 = pCurrent1->next;
}
else
{
pTail->next = pCurrent2;
pCurrent2 = pCurrent2->next;
}
pTail = pTail->next;
}
// 判断谁没有走完
if(pCurrent1 != NULL)
pTail->next =pCurrent1;
else if (pCurrent2 != NULL)
pTail->next =pCurrent2;
// 返回初始节点，要释放桥接的哨兵头
struct ListNode* head = pGuardHead->next;
free(pGuardHead);
pGuardHead = NULL;
return head;
}🙉【LeetCode】[206].反转链表
题目链接：206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 3：
输入：head = [] 输出：[]提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
🙊第一种解题思路：《取节点到新的链表》
// 第一种解题思路
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* pCurrent = head;
struct ListNode* newNode = NULL;
while(pCurrent != NULL)
{
// 保存pCurrent->指向的下一个位置。
struct ListNode* next = pCurrent->next;
// pCurrent->next 让他指向NULL，这是newNode还是空。
pCurrent->next = newNode;
// newNode指向pCurrent的位置。
newNode = pCurrent;
// pCurrent在继续往下移动
pCurrent = next;
}
// 程序走到这里就反转完成啦。
return newNode;
}🙊第二种解题思路：《反转链表指针方向》
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode *n1,*n2,*n3;
n1 = NULL;
n3 = NULL;
n2 = head;
while(n2 != NULL)
{
// n3记录下一个节点的位置。
n3 = n2->next;
// n2指向前面的节点。
n2->next = n1;
// 值传完，开始迭代。
n1 = n2;
n2 = n3;
}
return n1;
}🙉【LeetCode】[876].链表的中间节点
题目链接：876. 链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
// 慢指针一次走两步，快指针一次走一步
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
// 走完满指针就是中间值。
return slow;
}🙉【LeetCode】[22].链表中倒数第k个节点
题目链接：链表中倒数第k个结点牛客题霸牛客网 (nowcoder.com)
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
struct ListNode* slow = pListHead;
struct ListNode* fast = pListHead;
// fast 先走k步
while(k--)
{
// 如果说在fast先走k步的时候，出现空了，那么就会有问题了。
if(fast == NULL)
return NULL;
fast = fast->next;
}
// slow 和 fast一起走
while(fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
// 返回慢走的指针
return slow;
}🙉【LeetCode】[02.04].[分割链表]
题目链接：面试题 02.04. 分割链表
题目链接：链表分割牛客题霸牛客网 (nowcoder.com)
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
struct ListNode* partition(struct ListNode* head, int x)
{
struct ListNode* pSmallerGruad, *pSmallerTail; // 定较小的哨兵头，和尾指针
struct ListNode* pGreaterGruad, *pGreaterTail; // 定较大的哨兵头，和尾指针
// 判断是否开辟成功！
pSmallerGruad = pSmallerTail = (struct ListNode*)malloc(sizeof(struct ListNode));
if(pSmallerGruad == NULL)
{
perror("partition pSmallerGruad malloc fail!");
exit(-1);
}
else
{
pSmallerGruad->next = NULL;
}
pGreaterGruad = pGreaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
if(pGreaterGruad == NULL)
{
perror("partition pGreaterGruad malloc fail!");
exit(-1);
}
else
{
pGreaterGruad->next = NULL;
}
// 比哪里链表，小于x的和pSmallerGruad链接，大于x的和pGreaterGruad链接。
struct ListNode* pCurrent = head;
while(pCurrent != NULL)
{
if(pCurrent->val < x)
{
pSmallerTail->next = pCurrent;
pSmallerTail = pSmallerTail->next;
}
else
{
pGreaterTail->next = pCurrent;
pGreaterTail = pGreaterTail->next;
}
// 遍历节点继续前进。
pCurrent = pCurrent->next;
}
// 将较小的最后一个和较大的第一个进行链接，并且将较大的最后一个设为空。
pSmallerTail->next = pGreaterGruad->next;
pGreaterTail->next =NULL;
// 返还节点
head = pSmallerGruad->next;
// 释放空间。
free(pSmallerGruad);
pSmallerGruad = NULL;
free(pGreaterGruad);
pGreaterGruad = NULL;
return head;
}🙉【LeetCode】[234].回文链表
题目链接：234. 回文链表
题目链接：链表的回文结构牛客题霸牛客网 (nowcoder.com)
这道题我们可以采用之前写的函数。
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
// 查找中间节点。
struct ListNode* middleNode(struct ListNode* pHead)
{
struct ListNode* slow, * fast;
slow = fast = pHead;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next -> next;
slow = slow->next;
}
return slow;
}
// 反转节点。
struct ListNode* ReverseList(struct ListNode* pHead)
{
struct ListNode* newNode = NULL;
struct ListNode* pCurrent = pHead;
while (pCurrent != NULL)
{
struct ListNode* next = pCurrent->next;
pCurrent->next = newNode;
newNode = pCurrent;
pCurrent = next;
}
return newNode;
}
// 题目函数
bool isPalindrome(struct ListNode* head)
{
struct ListNode* pCurrent = head;
// 找节点的中间节点
struct ListNode* middle = middleNode(pCurrent);
/// 中间节点向后的节点逆置
struct ListNode* rMiddle = ReverseList(middle);
// 遍历整个链表，两两对比，只要一对不相等就不是回文链表。
while(pCurrent != NULL && rMiddle != NULL)
{
if(pCurrent->val != rMiddle->val)
return false;
pCurrent = pCurrent->next;
rMiddle = rMiddle->next;
}
return true;
}🙉【LeetCode】[160].相交链表
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案
提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
// 检测链表不是NULL链表。
if(headA == NULL || headB == NULL)
return NULL;
// 定义遍历节点变量。
struct ListNode* pCurrentA = headA;
struct ListNode* pCurrentB = headB;
// 求A组的长度
int lengthA = 0 ;
while(pCurrentA != NULL)
{
pCurrentA = pCurrentA->next;
lengthA++;
}
// 求B组的长度
int lengthB = 0;
while(pCurrentB != NULL)
{
pCurrentB = pCurrentB->next;
lengthB++;
}
// 判断是否相等
if(pCurrentA != pCurrentB)
{
return NULL;
}
// 假设A组的长，B组的短
struct ListNode* longList = headA;
struct ListNode* shortList = headB;
if(lengthA < lengthB) // 这里进行确认
{
longList = headB;
shortList = headA;
}
// 长的先走 差步
int excursion = abs(lengthA - lengthB);
while(excursion--)
{
longList = longList->next;
}
// 找第一个相同的节点，那个就是相交点。
while(longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
// 随便返回节点就行。
return longList;
}🙉【LeetCode】[141].环形链表
题目链接：141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
提示：
链表中节点的数目范围是
[0, 104]
-105 <= Node.val <= 105
pos为-1或者链表中的一个 有效索引 。
bool hasCycle(struct ListNode *head)
{
struct ListNode *fast, *slow;
fast = slow = head;
// fast走两步，slow走一步。
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
// 如果fast走到空了，那就说明不是环形了。
return false;
}
// 延申：
// 请证明一下，slow一次走一步，fast一次走两步？
// 请证明一下，slow一次走一步，fast一次走三步？
// 请证明一下，slow一次走一步，fast一次走N步？
// 请证明一下，slow一次走M步，fast一次走N步？(M<N)🙉【LeetCode】[142].环形链表 II
题目链接：142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
提示：
链表中节点的数目范围在范围
[0, 104]内
-105 <= Node.val <= 105
pos的值为-1或者链表中的一个有效索引
🙊第一种解题思路：《公式证明》
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *slow, *fast;
slow = fast = head;
// 先找到slow和fast的相交点。
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
// 找到相交点
if(fast == slow)
{
struct ListNode* pCurrent = head;
struct ListNode* meet = slow;
// pCurrent 和 meet 相等就是入口点。
while(meet != pCurrent)
{
meet = meet->next;
pCurrent = pCurrent->next;
}
return meet;
}
}
return NULL;
}🙊第二种解题思路：《转换成相交问题》
利用相交的函数。
// 利用链表相交的函数。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
// 检测链表不是NULL链表。
if(headA == NULL || headB == NULL)
return NULL;
// 定义遍历节点变量。
struct ListNode* pCurrentA = headA;
struct ListNode* pCurrentB = headB;
// 求A组的长度
int lengthA = 0 ;
while(pCurrentA != NULL)
{
pCurrentA = pCurrentA->next;
lengthA++;
}
// 求B组的长度
int lengthB = 0;
while(pCurrentB != NULL)
{
pCurrentB = pCurrentB->next;
lengthB++;
}
// 判断是否相等
if(pCurrentA != pCurrentB)
{
return NULL;
}
// 假设A组的长，B组的短
struct ListNode* longList = headA;
struct ListNode* shortList = headB;
if(lengthA < lengthB) // 这里进行确认
{
longList = headB;
shortList = headA;
}
// 长的先走 差步
int excursion = abs(lengthA - lengthB);
while(excursion--)
{
longList = longList->next;
}
// 找第一个相同的节点，那个就是相交点。
while(longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
// 随便返回节点就行。
return longList;
}
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *slow, *fast;
slow = fast = head;
// 先找到slow和fast的相交点。
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* entrance = getIntersectionNode(head,next);
meet->next = next; // 恢复节点
return entrance;
}
}
return NULL;
}🙉【LeetCode】[138].复制带随机指针的链表
题目链接：138. 复制带随机指针的链表
给你一个长度为 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 作为传入参数。
提示：
0 <= n <= 1000-104 <= Node.val <= 104Node.random为null或指向链表中的节点。
先看一下解题思路：
🙈第一步代码的实现
🙈第二步代码的实现
🙈第三步代码的实现
🙈完整代码
struct Node* copyRandomList(struct Node* head)
{
// 1、插入copy的节点
struct Node* pCurrent = head;
struct Node* copy = NULL;
struct Node* next = NULL;
while(pCurrent != NULL)
{
next = pCurrent->next; // 记录pCurrent的下一个节点。
copy = (struct Node*)malloc(sizeof(struct Node)); // 创建新的节点。
copy->val = pCurrent->val; // 值拷贝
// 插入pCurrent 和 pCurrent->next中间
pCurrent->next = copy;
copy->next = next;
// 迭代；
pCurrent = next;
}
// 2、更新copy的random
pCurrent = head;
while(pCurrent != NULL)
{
copy = pCurrent->next;
// 更新random有两种情况：
// 1、如果原节点random是NULL 那么拷贝节点的random也是NULL
// 2、如果源节点random不是NULL 那么拷贝节点的random就是源节点的下一个节点。
if(pCurrent->random == NULL)
copy->random = NULL;
else
copy->random = pCurrent->random->next;
// 迭代
pCurrent = copy->next;
}
// 3、copy节点要摘下来链接在一起，恢复原节点。
pCurrent = head;
struct Node* copyHead = NULL;
struct Node* copyTail = NULL;
while(pCurrent)
{
// 定义位置。
copy = pCurrent->next;
next = copy->next;
// 取节点尾插
// 1、还没有任何节点
// 2、已经右节点了
if(copyTail == NULL)
copyHead = copyTail = copy;
else
{
copyTail->next = copy;
copyTail = copyTail->next;
}
// 恢复原链表
pCurrent->next = next;
// 迭代
pCurrent = pCurrent->next;
}
return copyHead;
}