网站空间购买哪家好,沂南网站设计,注册域名费用一般多少钱,货运代理东莞网站建设C刷题 – 链表 文章目录 C刷题 -- 链表1.删除链表的倒数第 N 个结点2.链表相交3.环形链表 1.删除链表的倒数第 N 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
快慢指针的应用
fast指针先移动N步#xff0c;slow依然指向head#xff1b;然后fa…C刷题 – 链表 文章目录 C刷题 -- 链表1.删除链表的倒数第 N 个结点2.链表相交3.环形链表 1.删除链表的倒数第 N 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
快慢指针的应用
fast指针先移动N步slow依然指向head然后fast和slow同时移动直到fast指向链表最后一个节点的next也就是空此时slow就指向了倒数第N个节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if(head nullptr || head-next nullptr){return nullptr;}ListNode* fast head;ListNode* slow head;ListNode* prev nullptr;//fast指针先移动N步slow依然指向headfor(int i 0; i n; i){fast fast-next;}//然后fast和slow同时移动直到fast指向链表最后一个节点的next也就是空此时slow就指向了倒数第N个节点while(fast){fast fast-next;prev slow;slow slow-next;}if(prev) {prev-next slow-next;delete(slow);}else // 如果prev为空则删除的是头结点{prev head;head head-next;delete(prev);}return head;}
};2.链表相交
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
两个链表相交之后的部分一定是相同的可以分别计算两个链表的长度然后计算长度差让两个链表从末尾对齐如下图所示指针curA和curB同时向后遍历直到两者的指针地址相同
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int cntA 0, cntB 0;ListNode* curA headA;ListNode* curB headB;//遍历得到AB的长度while(curA){cntA;curA curA-next;}while(curB){cntB;curB curB-next;}//计算长度差让长链表先走int skip abs(cntA - cntB);ListNode* longerList headA;ListNode* shorterList headB;if(cntA cntB){swap(longerList, shorterList);}curA longerList;curB shorterList;while(skip--){curA curA-next;}//两个指针一起走while(curA ! curB){curA curA-next;curB curB-next;}return curA;}
};3.环形链表
https://leetcode.cn/problems/linked-list-cycle-ii/description/
判断链表是否有环
快慢指针分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点如果 fast 和 slow指针在途中相遇 说明这个链表有环fast指针一定先进入环中如果fast指针和slow指针相遇的话一定是在环中相遇这是因为fast是走两步slow是走一步其实相对于slow来说fast是一个节点一个节点的靠近slow的所以fast一定可以和slow重合
找到这个环的入口
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 -那么相遇时 slow指针走过的节点数为: x y fast指针走过的节点数x y n (y z)n为fast指针在环内走了n圈才遇到slow指针 yz为 一圈内节点的个数A。因为fast指针是一步走两个节点slow指针一步走一个节点 所以 fast指针走过的节点数 slow指针走过的节点数 * 2 (x y) * 2 x y n (y z)两边消掉一个xy: x y n (y z)因为要找环形的入口那么要求的是x因为x表示 头结点到 环形入口节点的的距离。将x单独放在左面x n (y z) - y再从n(yz)中提出一个 yz来整理公式之后为如下公式x (n - 1) (y z) z 注意这里n一定是大于等于1的因为 fast指针至少要多走一圈才能相遇slow指针先拿n为1的情况来举例意味着fast指针在环形里转了一圈之后就遇到了 slow指针了。 当 n为1的时候公式就化解为 x z这就意味着从头结点出发一个指针从相遇节点 也出发一个指针这两个指针每次只走一个节点 那么当这两个指针相遇的时候就是 环形入口的节点。也就是在相遇节点处定义一个指针index1在头结点处定一个指针index2。 让index1和index2同时移动每次移动一个节点 那么他们相遇的地方就是 环形入口的节点。那么 n如果大于1是什么情况呢就是fast指针在环形转n圈之后才遇到 slow指针。 其实这种情况和n为1的时候 效果是一样的一样可以通过这个方法找到 环形的入口节点只不过index1 指针在环里 多转了(n-1)圈然后再遇到index2相遇点依然是环形的入口节点。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast head;ListNode* slow head;while(fast fast-next) //如果没有环fast或者fast-next就会为空{fast fast-next-next; //快指针一次走两步slow slow-next; //慢指针一次走一步//若有环则fast和slow会在环内相遇if(fast slow){//两个指针从相遇节点和头节点同时向后走最终的相遇点就是环的入口ListNode* index1 head;ListNode* index2 fast;while(index1 ! index2){index1 index1-next;index2 index2-next;}return index2;}}return nullptr;}
};
