绍兴企业网站开发,网络营销导向型企业网站建设的原则,网站行高,随州网站建站文章目录 一、链表相交问题二、单链表判环问题三、回文链表四、重排链表结点 初学双指针的同学#xff0c;请先弄懂删除链表的倒数第 N 个结点。 并且在学习这一节时#xff0c;不要将思维固化#xff0c;认为只能这样做#xff0c;这里的做法只是技巧。 一、链表相交问题 … 文章目录 一、链表相交问题二、单链表判环问题三、回文链表四、重排链表结点 初学双指针的同学请先弄懂删除链表的倒数第 N 个结点。 并且在学习这一节时不要将思维固化认为只能这样做这里的做法只是技巧。 一、链表相交问题
LeetCode160.相交链表 题目要求时间复杂度为O(L1L2)空间复杂度为O(1)实际上并不是说只能遍历一次单个链表遍历常数次时间复杂度仍为O(L)。我们可以采用如下方法解决 计算两个链表的长度首先遍历两个链表计算它们各自的长度lenA和lenB同时检查链表的末尾节点是否相同。如果末尾节点不同则两个链表不相交直接返回NULL。这一步也确保了如果两个链表相交它们的末尾节点必定是相同的。对于存在相交的链表它们的的末尾结点一定是一样的 调整起点为了同步遍历两个链表找到交点需要从两个链表相同的“距离”开始遍历。由于两个链表可能长度不同我们先计算长度差abs(lenA-lenB)。然后让较长的链表的指针先前进这个长度差的步数。这样做的目的是让两个链表的指针能够在同一起跑线上“开始比赛”。 同步前进直到找到交点之后同时前进两个链表的指针直到它们相遇。由于步骤2已经确保了两个指针距离链表末尾的距离相同所以它们会在交点相遇。如果两个链表有交点那么这个交点是两个指针第一次相遇的地方。
这段代码的关键在于通过计算长度差并同步前进两个指针来找到可能的交点。这种方法不需要修改链表结构也不需要额外的存储空间效率较高。在最坏的情况下时间复杂度是O(L1L2)其中L1和L2分别是两个链表的长度。
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//if(!headA||!headB) return NULL;int lenA0,lenB0;ListNode * travelAheadA,* travelBheadB;while(travelA-next||travelB-next){if(travelA-next) {travelAtravelA-next;lenA;}if(travelB-next) {travelBtravelB-next;lenB;}}if(travelA!travelB) return NULL;if(lenBlenA) swap(headA,headB);lenAabs(lenA-lenB);//复用for(int i0;ilenA;i) headAheadA-next;while(headA!headB){headAheadA-next;headBheadB-next;}return headA;}
};防止大脑已经不会暴力暴力解法 ①对于L1从头遍历L1的每一个结点判断该结点是否在L2中如果在则是相交结点。从头遍历第一个在的是相交结点如果每次都遍历一次L2则时间复杂度O(L1*L2) ②无脑的哈希优化将L2的结点存入一个哈希表集合每次判断时只平均需要O(1)的时间所以时间复杂度为O(L1L2)空间复杂度O(L2)。 哈希优化
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//if(!headA||!headB) return NULL;unordered_setListNode * Set;while(headA){Set.insert(headA);headAheadA-next;}while(headB){if(Set.count(headB)) return headB;headBheadB-next;}return NULL;}
};二、单链表判环问题
LeetCode141.环型链表 题目要求使用空间复杂度为O(1)因此不能用哈希解决用哈希只需要遍历的过程中将结点存入哈希表每次遍历先判断该结点是否在哈希表中如果不在则存入哈希表如果在则找到环。但是哈希表的空间复杂度为O(L)因此我们只能用其他方法。 这里使用双指针一个慢指针slow一个快指针fastslow一次走一步fast一次走两步。类似于跑步比赛从同一个长道出发跑向运动场的跑道上跑步由于快指针跑的速度是慢指针的两倍快指针总会多跑一圈然后超过慢指针。 因此如果只需要判断是否存在环只需要这样做无环的话fast一定先跑到底
class Solution {
public:bool hasCycle(ListNode *head) {if(!head||!head-next) return false;ListNode * slowhead;ListNode * fasthead;while(fast!nullptr fast-next!nullptr){slowslow-next;fastfast-next-next;if(fastslow) return true;}return false;}
};不过我们知道在行走时还有信息我们没有用到我们是否能利用这些信息找到环的入口呢信息
慢指针走的步数step_slow快指针走的步数step_fast则有step_faststep_slow*2。假设环外结点数为a环中结点数为b设x是fast和slow相遇时离换入口的距离则step_fastanbxstep_slowacbx0xb。联立可得①anbx2a2x2cb②nbax2cb③(n-2c)bax。由③可知ax0且ax是圈中结点数的倍数换句话说由于现在走到的位置是x则在fast和slow相遇的位置再走a步可以走到环的入口因为再走这么多步刚好是环的倍数步换句话说如果现在有一个指针p从环外起点出发每次走一步与fast或slow一同行走走完环外结点个数步a步之后会在环的入口处相遇
寻找环的入口
ListNode *detectCycle(ListNode *head) {ListNode *slow head, *fast head;// 第一次遍历找到快慢指针相遇点while (fast ! nullptr fast-next ! nullptr) {slow slow-next;fast fast-next-next;if (slow fast) { // 发现环// 将其中一个指针这里选择slow移回头节点slow head;// 两个指针以相同速度移动再次相遇点即为环入口while (slow ! fast) {slow slow-next;fast fast-next;}return slow; // 返回环入口}}return nullptr; // 无环
}三、回文链表
LeetCode234.回文链表 回文链表我们可以这样做我们单独存一个原链表的反置之后的链表然后反置的 和 原链表 从首位置开始齐步向前就行。当然逆序的话使用栈也是可以的栈就相当于你存进去的东西想逆着拿出来换句话说你只需要逆序来查看某个东西的元素存入栈是很好的选择不过时间复杂度需要的是O(1)我们需要一点点技巧。但是单链表怎么也不可能反着遍历呀怎么办呢 将中点之后的链表部分翻转吧朋友找到链表中点然后将后面的链表翻转然后就可以首尾齐进了。翻转链表只需要O(1)的时间复杂度三个指针~不过如果原题说不允许修改原结构那就再翻转过了即可虽然输入和输出只是一个接口但是这确实只能说很离谱。
反转链表的后半部分
找到中点使用快慢指针找到链表的中间节点。反转后半部分从中间节点开始反转链表的后半部分。比较前后半部分将前半部分和反转后的后半部分进行比较如果每个节点的值都相同则链表是回文。恢复链表可选如果需要保持原链表的结构可以再次反转后半部分以恢复原链表。
这种方法的空间复杂度为O(1)但需要改变链表结构如果不恢复的话。
class Solution {
public:bool isPalindrome(ListNode* head) {if (head nullptr) {return true;}// 找到前半部分链表的尾节点并反转后半部分链表ListNode* firstHalfEnd endOfFirstHalf(head);ListNode* secondHalfStart reverseList(firstHalfEnd-next);// 判断是否回文ListNode* p1 head;ListNode* p2 secondHalfStart;bool result true;while (result p2 ! nullptr) {if (p1-val ! p2-val) {result false;}p1 p1-next;p2 p2-next;} // 还原链表并返回结果firstHalfEnd-next reverseList(secondHalfStart);return result;}ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* curr head;while (curr ! nullptr) {ListNode* nextTemp curr-next;curr-next prev;prev curr;curr nextTemp;}return prev;}ListNode* endOfFirstHalf(ListNode* head) {ListNode* fast head;ListNode* slow head;while (fast-next ! nullptr fast-next-next ! nullptr) {fast fast-next-next;slow slow-next;}return slow;}
};四、重排链表结点 这个和回文链表是一样的将中点之后的链表部分翻转然后就可以一个一个选了。
