网站运营推广难做吗,网站备案后,石家庄怎样做网站,wordpress 解释符号欢迎各位来到 Harper.Lee 的学习世界#xff01; 博主主页传送门#xff1a;Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦#xff01; 一、力扣--141. 环形链表 题目描述#xff1a;给你一个链表的头节点 head #xff0c;判断链表中是否有环。如果链表中有某个… 欢迎各位来到 Harper.Lee 的学习世界 博主主页传送门Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦 一、力扣--141. 环形链表 题目描述给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。 常见环形链表有以下几种环形链表不清楚最后一个节点即尾节点在哪里的。 常见的判断链表是否带环的错误方法方法1. 判断遍历的指针的next指针是否为进环时的第一个节点指针。错误原因是首先我们不清楚用来遍历的指针是否进环此外环外的部分很长也可能比较短什么时候进环不能确定。方法2. 判断尾节点的next指针是否为空。错误原因如果链表是带环的我们并不能知道谁是最后一个节点也可以说是带环链表没有尾节点。
最好的办法就是使用快慢指针追击慢指针slow一次走一步快指针fast一次走两步。当 bool hasCycle(struct ListNode *head) {struct ListNode* slow head,*fast head;while(fast fast-next){slow slow-next;fast fast-next-next;//两个nextif(slow fast)return true;}return false;
}
Q1为什么一定会相遇 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情况因此在满指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。
Q2快指针一次走3步走4步...n步行吗 根据分析可知快慢指针的追击问题不在于两者一次走多少步而在于快慢指针之间的速度差。
分析过程图片 Q3有没有可能会错过永远追不上
分析过程图片 所以答案是一定会追上一定能追上
二、力扣--142. 环形链表 II 题目描述给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改 链表。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow head, *fast head;while(fast fast-next){slow slow-next;fast fast-next-next;//两个next两步//相遇if(slow fast){struct ListNode* meet slow;while(meet ! head){meet meet-next;head head-next;}return meet;}}return NULL;
}
三、力扣---02.02. 返回倒数第 k 个节点
思路一创建一个新数组在数组中寻找相应的数据返回数据对应的下标。空间复杂度高了
思路二第一遍遍历得出节点个数n如果要求找倒数第k个节点就去找正数第n-k1个节点并返回该节点的值。
思路三在思路二的基础上要求空间复杂度O1也就是只能遍历链表一遍快慢指针法。fast先走k步拉开差距然后两个指针再同时移动。注意单链表是不能倒着走的。可以加一个判断k小于等于链表长度。
int kthToLast(struct ListNode* head, int k){struct ListNode* fast head,*slow head;//均是从头节点开始///快指针先走k步或者k-1步while(k--){fast fast-next;}while(fast)//快慢指针同时走快指针先走到头{slow slow-next;fast fast-next;}return slow-val;
}四、牛客--OR36 链表的回文结构 题目描述对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。如1-2-2-1返回true。
单链表有奇数个和偶数个两种情况1、先查找中间节点2、后半段逆置。 代码如下
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//查找中间节点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head,*fast head;while(fast fast-next){slow slow-next;fast fast-next;}return slow;
}struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur head;struct ListNode* newhead NULL;while (cur){struct ListNode* next cur-next;//头插cur-nextnewhead;newhead cur;cur next;}return newhead;
}bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);//查找中间节点struct ListNode* rmid reverseList(mid);//逆置后半段while(rmid A)//有一个为空就结束了则都不为空进入循环{if(rmid-val!A-val)return false;rmid rmid-next;}return true;}
};
五、力扣--160. 相交链表 题目描述给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。图示两个链表在节点 c1 开始相交 链表的相交的形式不是X字型而是Y字型 因为单链表的一个节点只能有一个next指针。 思路一A链表逐个结点与B链表比较如果存在相等则就是相交结点注要比较指针而不能比较值因为值是可以重复的。 具体过程分析1. 判断两个链表是否相交判断两个链表的尾指针是否相等相等则两个链表相交注意用地址来判断而不是值。2. 若相交找出第一个交点用暴力求解链表A的节点依次和链表B的所有节点比较一遍比较地址而不是值如果链表A的某个节点和链表B相等则这个节点就是交点。 最坏情况不相交时间复杂度Om*n两个链表的长度。 思路二长的链表往前走长度差到短链表开头再同时走直到相等就是相交点。 最坏的情况最后一个才遇到交点。Fn3*N时间复杂度ON。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA headA,*curB headB;int lenA 1,lenB 1;//计算链表长度while(curA-next){curA curA-next;lenA;}while(curB-next){curB curB-next;lenB;}//尾节点不相等就是相交if(curA ! curB){return NULL;}//长链表先走差距步两个链表再同时走第一个相等就是交点//假设法让逻辑更加简单int gap abs(lenA - lenB);struct ListNode* longList headA,*shortList headB;if(lenB lenA){longList headB;shortList headA;}while(gap--){longList longList-next;}while(longList ! shortList){longList longList-next;shortList shortList-next;}return shortList;
} 创作不易喜欢的uu三连支持一下叭
