软件下载网站排行,住房和城乡建设部办公厅网站,网站色调搭配,网页友情链接为了加深对环形链表的理解和掌握#xff0c;这两道题是很不错的选择。 这里所说环形链表不是一个圈圈的结构#xff0c;而是带环链表。 链接#xff1a;环形链表#xff08;1#xff09; 注意这里链表的长度 所以要注意链表是否为空 第一种方法#xff0c;应该是比较容易… 为了加深对环形链表的理解和掌握这两道题是很不错的选择。 这里所说环形链表不是一个圈圈的结构而是带环链表。 链接环形链表1 注意这里链表的长度 所以要注意链表是否为空 第一种方法应该是比较容易想到的方法偷鸡取脚 遍历链表将每个节点的val更改为一个不容易想到的值如666666当遇到一个666666时就返回true如果在遍历过程中一直走到空都再没有遇到一个666666那就返回false。 代码如下 bool hasCycle(struct ListNode *head) {struct ListNode*phead;while(p){if(p-val!666666){p-val666666;pp-next;}else return true;}return false;
}这种方法明显是投机取巧所以还有可能被抓到。 运行后还是也可以通过 双指针法正经方法 就想操场的跑道上有跑的快的人和跑得慢的人快的人会不断追上慢的人。 设置双指针从head开始走快指针一次跑两步慢指针一次跑一步链表中是有环的快指针一定会抓到慢指针。 在慢指针进环时快指针已经在环状里转圈圈了慢指针一次走一步快指针一次走两步慢指针走半圈快指针就走一圈。 代码如下 bool hasCycle(struct ListNode *head) {struct ListNode*slowhead,*fasthead;while(fastfast-next){fastfast-next-next;slowslow-next;if(slowfast){return true;}}return false;
}一直找找找如果有环一定会相遇。 思考 如果快指针一次走3步还可以保证能抓到慢指针吗 假使慢指针进环时快慢指针差距m个位置每次快指针与慢指针的距离差距减小为2有两种情况。 m为偶数 每次距离都减小2 m-2 m-4 m-6 … 4 2 0 最终快指针会遇到慢指针。 2. m为奇数 m-2 m-4 … 3 1 -1 当相差为-1时快慢指针间的距离变为了m-1。 假设C是环的长度这里的-1即为C-1如果环的长度为偶数那么快慢指针最近的距离为1因为一次减小的距离为2所以永远也追不上慢指针。 环形链表2 和第一道题不一样的是这道题如果有环就返回入环的第一个节点如果链表无环就返回NULL。 接下来就要进行分析 当快指针与慢指针相遇时快指针所走的路程是慢指针的两倍。 假设起点到入环口的距离是L圆环的长度为C入口点到相遇点的距离为x这时通过分析就可以列出一个等式。 快指针的路程是慢指针的二倍 2(LX)Ln( C )X 可得 LXn( C ) Ln( C -X; 设置两个指针第一个指针从起始位置出发另一个指针从相遇点出发他们就会在环的入口处相遇。 套用第一道题的思路快慢指针相遇时找到相遇点在设置两个指针分别出发直到相遇如果没有环的话就返回NULL; 代码如下 struct ListNode*fasthead;struct ListNode*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(slowfast){struct ListNode*meetslow;while(head!meet){headhead-next;meetmeet-next;}return meet;}}return NULL; } 提交后顺利通过。 环形链表的约瑟夫问题 链接 环形链表的约瑟夫问题 要使用单向链表实现。 分析题目构建一个链表依次储存节点的位置然后找到链表的尾尾的next等于头节点这样一个环形链表就构建成功了。 从第一个节点开始往后走m-1步数数时为m因为第一个节点数1所以往后走m-1到达目标节点保存这个节点的next将起始位置更改为该next然后从新的起始位置继续往后边数直到删除到只剩最后一个节点为止假设这个节点为hei那么循环结束的条件就是hei-nexthei判断条件就是hei-next!-hei。 要注意 看代码讲解很详细
#include stdio.h
#include stdlib.h
#include assert.htypedef struct ListNode
{int val;struct ListNode* next;
}LN;LN* Initnode()
{LN* head (LN*)malloc(sizeof(LN));head-next NULL;head-val 0;return head;
}LN* GetNewnode(int x)
{LN* newnode (LN*)malloc(sizeof(LN));newnode-next NULL;newnode-val x;return newnode;
}
void Pushnode(LN* head, int x)
{assert(head);LN* pre head;while (pre-next){pre pre-next;}pre-next GetNewnode(x);
}void Popnode(LN*head,LN* node)
{LN* cur head;while (cur-next ! node){cur cur-next;找到要删除的节点的前一个}LN* next node-next;cur-next next;free(node);node NULL;
}int main()
{int m, n;scanf(%d %d, m, n);//建立链表LN* head GetNewnode(1);//第一个编号为1for (int i 2; i m; i){Pushnode(head, i);//建立链表}//找尾LN* cur head;while (cur-next ! NULL){cur cur-next;}cur-next head;//环形链表弄完//数数删位LN* hei head;while (hei-next ! hei){for (int i 1; i n; i)//因为移动三步是移动量两次。{hei hei-next;}LN* pop hei;//找到要删除的节点pophei hei-next;//更换hei的位置Popnode(hei,pop);//删除pop。}printf(%d , hei-val);//打印留下的节点的数值。return 0;
}本文的讲解到这里就结束啦鄙人才识短浅如有错误还请多多指教。
