网站 建设 业务需求表,百度seo整站优化,app系统开发费用,seo优化论坛链表解题技巧
额外的数据结构#xff08;哈希表#xff09;#xff1b;快慢指针#xff1b;虚拟头节点#xff1b;
找到两个链表相交的第一个节点
给定两个链表#xff0c;这两个链表可能有环#xff0c;可能无环。判断这两个链表是否相交#xff0c;相交则返回第一…链表解题技巧
额外的数据结构哈希表快慢指针虚拟头节点
找到两个链表相交的第一个节点
给定两个链表这两个链表可能有环可能无环。判断这两个链表是否相交相交则返回第一个相交的节点不相交则返回nullptr。
首先需要判断两个链表是否有环有环的话入环节点的位置在哪
然后分情况判断两个链表是否相交
两个无环链表对于两个无环链表一个有环一个无环不可能相交两个有环链表入环点相同一定相交、入环点不相同
ListNode* LinkedList::findFirstIntersection(ListNode *head1, ListNode *head2) {if (head1 nullptr || head2 nullptr) {return nullptr;}// has cycleListNode *loop1 hasCycle(head1);ListNode *loop2 hasCycle(head2);// if (loop1 nullptr loop2 nullptr) return findFirstIntersectionWithNoLoop(head1, head2);if (loop1 ! nullptr loop2 ! nullptr) return findFirstIntersectionWithLoops(head1, loop1, head2, loop2);return nullptr;
}链表是否有环
方法1哈希表时O(N)空O(N)
使用哈希表在链表遍历过程中判断该节点是否在哈希表中
该节点在表中则说明有环此时为入环第一个节点返回该节点并退出该节点不在表中说明无环将节点指针加入表中继续遍历遍历到空则说明无环。
ListNode* LinkedList::hasCycleBySet(ListNode *head) {if (head nullptr || head-next nullptr) return nullptr;std::unordered_setListNode* set;ListNode *cur head;while (cur) {if (set.find(cur) ! set.end()) {return cur;}set.insert(cur);cur cur-next;}return nullptr;
}方法2快慢指针时O(N), 空O(1)
在快慢指针遍历链表的过程中如果快指针遍历到nullptr则说明无环。
如果有环快慢指针一定会在环内相遇当相遇发生之后快指针回到头节点慢指针不动快慢指针同时一次一步的移动直至相遇相遇的位置即为入环的第一个节点。
ListNode* LinkedList::hasCycle(ListNode *head) {if (head nullptr || head-next nullptr) return nullptr;ListNode *slow head;ListNode *fast head;while (fast ! nullptr fast-next ! nullptr) {slow slow-next;fast fast-next-next;if (slow fast) {fast head;while (fast ! slow) {slow slow-next;fast fast-next;}return slow;}}return nullptr;
}Notes
fast和slow必须同时从head出发fasthead-nextslowhead这样的出发就会差一个节点永远无法结束
链表相交
无环链表相交
最好理解和想到的方法就是遍历两个链表计算出两个链表的长度差值让长链表先移动差值步接着继续同时遍历直到相遇或都为nullptr。
ListNode* LinkedList::findFirstIntersectionWithNoLoop(ListNode *head1, ListNode *head2) {ListNode *cur1 head1;ListNode *cur2 head2;int diff 0;while (cur1) {cur1 cur1-next;diff;}while (cur2) {cur2 cur2-next;diff--;}cur1 diff 0 ? head1 : head2; // cur1 - the longer listcur2 cur1 head2 ? head1 : head2;diff diff 0 ? -diff : diff; // abs// cur1 move diff steps firstwhile (diff--) cur1 cur1-next;while (cur1 ! cur2) {cur1 cur1-next;cur2 cur2-next;}return cur1;
}或者使用交换遍历的方式因为无论如何两个链表都遍历的话最后要不就相交要不就都为nullptr。
注意两个节点和一个节点相交时的循环判断。
ListNode* LinkedList::findFirstIntersectionWithNoLoopEx(ListNode *head1, ListNode *head2) {ListNode *cur1 head1;ListNode *cur2 head2;while ( cur1 ! cur2 ) {cur1 cur1 ? cur1-next : head2;cur2 cur2 ? cur2-next : head1;}return cur1;
}有环链表相交
有环链表有入环节点相同和入环节点不同两种情况
入环节点相同的话肯定相交交点也一定在头节点到入环节点之间等价于无环链表相交入环节点不同的情况下如果相交则这两个节点一定都在一个环上从其中一个节点开始遍历到回到这个节点的过程中如果没有遇到另外一个节点则说明不相交反之相交随意返回其中一个节点即可。
ListNode* LinkedList::findFirstIntersectionWithLoops(ListNode *head1, ListNode *loop1, ListNode *head2, ListNode *loop2) {if (loop1 loop2) {ListNode *cur1 head1;ListNode *cur2 head2;while (cur1 ! cur2) {cur1 cur1-next loop1-next ? head2 : cur1-next;cur2 cur2-next loop1-next ? head1 : cur2-next;}return cur1;} else {ListNode *cur loop1-next;while (cur ! loop1) {cur cur-next;if (cur loop2) return cur;}return nullptr;}
}
