注册企业在哪个网站,成都活动策划公司,wordpress防采集插件,制作网站工具#x1f493;作者简介#x1f44f;#xff1a;在校大二迷茫大学生 #x1f496;个人主页#x1f389;#xff1a;小李很执着 #x1f497;系列专栏#xff1a;Leetcode经典题 每日分享#xff1a;人总是在离开一个地方后开始原谅它❣️❣️❣️———————————… 作者简介在校大二迷茫大学生 个人主页小李很执着 系列专栏Leetcode经典题 每日分享人总是在离开一个地方后开始原谅它❣️❣️❣️———————————————— 目录 ❣️1.206.反转链表
1.题目
2.解答
1.遍历法 2.头插法
❣️2. 牛客.链表中倒数第k个结点
1.题目
2.解答 ❣️ 3.160.相交链表
1.题目
2.解答 ❣️4.141.环形链表
1.题目
2.解答 ❣️1.206.反转链表
1.题目
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 1 输入head [1,2,3,4,5] 输出[5,4,3,2,1] 示例 2 输入head [1,2] 输出[2,1] 示例 3
输入head [] 输出[]
提示
链表中节点的数目范围是 [0, 5000] -5000 Node.val 5000 2.解答
1.遍历法 创建3个指针n1、n2、n3分别指向反转后的头节点、当前节点初始化为head、当前节点的后一个节点。初始化n1为NULL。 进入循环循环条件为n2非NULL。在循环中首先将n2指向n1实现当前节点的反转。 然后让n1指向n2将n1更新为反转后的头节点。 再让n2指向n3将当前节点指向下一个节点。 如果n3非NULL则让n3指向其下一个节点。 循环结束后返回n1即为反转后的头节点。 这里值得注意的是需要先判断head是否为NULL如果是则直接返回NULL否则会出现空指针异常。 struct ListNode* reverseList(struct ListNode* head)
{
if(head NULL)
return NULL;
struct ListNode* n1,*n2,*n3;
n1 NULL;
n2 head;
n3 head-next;
while(n2)
{
n2-next n1;
n1 n2;
n2 n3;
if(n3)
n3 n3-next;
}
return n1;
}2.头插法 从头节点 head 开始遍历链表每次将当前节点 cur 的 next 指针指向新链表的头节点 newhead然后将 newhead 更新为 cur最后将 cur 移向下一个节点。这相当于不断将原链表的节点从头部插入到新链表中从而实现了链表的反转。 最终返回新链表的头节点 newhead即为原链表反转后的链表头。 struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur head;
struct ListNode* newhead NULL;
while(cur)
{
struct ListNode* next cur-next;// 头插
cur-next newhead;
newhead cur;
cur next;
}
return newhead;
}❣️2. 牛客.链表中倒数第k个结点
1.题目
描述 输入一个链表输出该链表中倒数第k个结点。 示例1 输入 1,{1,2,3,4,5} 返回值 {5}
2.解答 定义两个指针slow和fast初始都指向链表头节点pListHead。 让fast先走k步如果fast为空则返回NULL因为链表长度小于k找不到倒数第k个节点。 然后slow和fast同时走直到fast到达链表末尾。 最后返回slow所指向的节点即可。 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ){struct ListNode* slow pListHead,*fast pListHead;// write code here
// fast先走k步
while(k--)
{
if(fast NULL)
return NULL;fast fast-next;
}
// 同时走
while(fast)
{
slow slow-next;
fast fast-next;
}
return slow;} ❣️ 3.160.相交链表
1.题目
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交
题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
自定义评测
评测系统 的输入如下你设计的程序 不适用 此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中从头节点开始跳到交叉节点的节点数 skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 示例 1
输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at 8 解释相交节点的值为 8 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。 在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。 — 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。
示例 2 输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1 输出Intersected at 2 解释相交节点的值为 2 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [1,9,1,2,4]链表 B 为 [3,2,4]。 在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。 示例 3 输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2 输出null 解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。 由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。 这两个链表不相交因此返回 null 。
提示
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]
2.解答 函数首先遍历链表A和链表B找到它们的尾结点并计算它们的长度。如果两个链表的尾结点不同则它们不可能相交直接返回NULL指针。 如果两个链表相交则它们必须有共同的尾部。接下来找到两个链表的差距记为n。如果链表B的长度大于链表A则将longList指向链表BshortList指向链表A否则将longList指向链表AshortList指向链表B。然后让longList先走n步然后longList和shortList一起走直到它们相遇即为它们的交点。 最后返回交点的地址。 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){
struct ListNode* curA headA,*curB headB;
int lenA 1,lenB 1;
// 找尾结点顺便算一下长度
while(curA-next)
{
lenA;
curA curA-next;
}
while(curB-next)
{
lenB;
curB curB-next;
}
//判断相交
if(curA ! curB)
{
return NULL;
}
int n abs(lenA-lenB);
struct ListNode* longList headA,*shortList headB;
if(lenB lenA)
{
longList headB;
shortList headA;
}
// 长的先走差距步
while(n--)
{
longList longList-next;
}
// 同时走
while(longList ! shortList)
{
longListlongList-next;
shortListshortList-next;
}
return longList;} ❣️4.141.环形链表
1.题目
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 示例 1 输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出true
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出false
解释链表中没有环。提示
链表中节点的数目范围是 [0, 104]-105 Node.val 105pos 为 -1 或者链表中的一个 有效索引 。
2.解答 定义两个指针slow和fast初始值均指向head节点。在循环中slow每次移动一步fast每次移动两步如果存在环那么fast最终一定会追上slow。在每次移动后判断slow和fast是否指向同一个节点如果是则存在环返回true。如果循环结束后仍然没有找到环则不存在环返回false。 因为快指针每次移动两步慢指针每次移动一步所以如果存在环快指针一定可以追上慢指针。而如果不存在环快指针最终会到达链表尾部循环结束。 bool hasCycle(struct ListNode *head){
struct ListNode*slow head,*fast head;
while(fast fast-next)
{
slow slow-next;
fast fast-next-next;
if(slow fast)
return true;
}
return false;
}
