哪个网站可以做试卷,重庆专业做网站公司,wordpress增加论坛,友情链接交换网目录
一、环形链表
题一#xff1a;环形链表
思路#xff1a;
思考一#xff1a;为什么#xff1f;
思考二#xff1a;快指针一次走3步、4步、......n步#xff0c;能否相遇
step1#xff1a;
step2#xff1a;
代码#xff1a;
题二#xff1a; 环形链表 I…目录
一、环形链表
题一环形链表
思路
思考一为什么
思考二快指针一次走3步、4步、......n步能否相遇
step1
step2
代码
题二 环形链表 II
思路
思考为什么
代码
二、随机链表的复制
思路
步骤一
步骤二新结点的随机指向结点
步骤三链接新结点
代码 一、环形链表
题一环形链表
https://leetcode.cn/problems/linked-list-cycle/description/
思路
使用快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表的头结点往下走则一定会在环形链表的环中相遇。
思考一为什么
设慢指针为 slow 快指针为 fast 头结点到入环点的长度为 L环的长度为 C 则当 slow 到达入环点时从 fast 到达 slow 的长度为 N 则 slow 到达入环点后 slow 和 fast 在环内行走则 此时变为追击问题快指针一次走两步慢指针一次走一步没走一步快慢指针之间的距离减一即NN-1N-2N-3......3210两指针相遇。
思考二快指针一次走3步、4步、......n步能否相遇
step1
当快指针一次走三步时每走一步两指针之间的距离缩小两步此时分为两种情况
N为偶数NN-2N-4N-6......420两指针相遇 N为奇数NN-2N-4N-6......31-1两指针错开进入新一轮追击此时两指针之间的距离变为 C -1 C-1
此时若 C-1也分两种亲情况
C-1为偶数则 C-1 类似于 N为偶数两指针相遇C-1为奇数则 C-1 类似于 N为奇数两指针错开那么两者便一直不会相遇
总结当N为奇数C为偶数时两指针 有可能 不会相遇
step2 还是这张图当 slow 到达入环点时假设 fast 已经走了x*C圈则从中可以得到两指针所走的路程
fastLx*CC-NslowL
又因为慢指针一次走一步快指针一次三步由此可以得出方程式
3*Sslow Sfast ----- 3*L Lx*CC-N----- 2*L (x1)*C-N
因为 2*L 一定为偶数这满足方程式的情况有两种
偶数 偶数 - 偶数偶数 奇数 - 奇数
因此当 N 为偶数时(x1)*C一定为偶数即 C 为偶数当 N 为奇数时(x1)*C一定为奇数即 C 为奇数不存在step1中 N为奇数C为偶数 的情况则两指针一定会相遇。快指针一次走4、5、......n步同样如此证明。
结论快指针一次不管走多少步都一定会与慢指针相遇
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode LN;
bool hasCycle(struct ListNode *head) {LN* slow,*fast;slow fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){return true;}}return false;
}
题二 环形链表 II
https://leetcode.cn/problems/linked-list-cycle-ii/description/
思路
让一个指针从头结点开始遍历链表同时让一个指针从 判定该链表为环形链表的相遇点开始绕环运行两个指针都是每次只走一步最终一定会在入口点相遇
思考为什么
设头结点为 H 入环点为 E H 到 M 的距离为 L快慢指针相遇点为 M E 到 M 的距离为 X 环的长度为 R 则 则快慢指针相遇时快fast慢slow指针相遇时假设快指针已经绕环走了 n 圈则两指针走过的路程
fast LXn*RslowLX
取快指针一次两步慢指针一次一步可得方程式
LXn*R LX
化简得 L n*R-X
即 L (n -1)*R(R-X)n取1234......
当n 1时L R-X则 则 让一个指针从头结点开始遍历链表同时让一个指针从 判定该链表为环形链表的相遇点开始绕环运行两个指针都是每次只走一步最终一定会在入口点相遇、
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode LN;
struct ListNode *detectCycle(struct ListNode *head) {LN* slow,*fast;slow fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){slow head;while(slow ! fast){slow slow-next;fast fast-next;}return slow;}}return false;
}
二、随机链表的复制
https://leetcode.cn/problems/copy-list-with-random-pointer/description/
思路
步骤一
遍历原链表根据结点保存的数据申请并复制到新的结点并且插入到该节点后。 步骤二新结点的随机指向结点
赋值 新结点的随机指向结点 原链表结点的随机指向结点的下一个结点 步骤三链接新结点 代码
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/
typedef struct Node Node;
//申请新结点
Node* BuyNode(int val)
{Node* newNode (Node*)malloc(sizeof(Node));newNode-val val;newNode-next NULL;newNode-random NULL;return newNode;
}
//插入原链表
void PushNode(Node* pNode)
{Node* pcur pNode;while(pcur){Node* pNext pcur-next;Node* newNode BuyNode(pcur-val);newNode-next pNext;pcur-next newNode;pcur pNext;}
}
struct Node* copyRandomList(struct Node* head) {if(head NULL){return head;}//插入原链表PushNode(head);//拷贝randomNode* pcur head;while(pcur){Node* pcpy pcur-next;if(pcur-random ! NULL){pcpy-random pcur-random-next;}pcur pcpy-next;}//链接新链表Node *newHead,*newTail;pcur head;newHead newTail pcur-next;while(pcur-next-next){pcur pcur-next-next;newTail-next pcur-next;newTail pcur-next;} return newHead;
}
