免费劳务网站建设,开发商违约延期交房可以退房吗,线上购物网站建设成本,苏州建设网站市政中标项目目录
题一#xff1a;环形链表
思路一#xff1a;
题二#xff1a;复制带随机指针的链表 思路一#xff1a;
本人实力有限可能对一些地方解释的不够清晰#xff0c;可以自己尝试读代码#xff0c;望海涵#xff01; 题一#xff1a;环形链表
给定一个链表的头节点…
目录
题一环形链表
思路一
题二复制带随机指针的链表 思路一
本人实力有限可能对一些地方解释的不够清晰可以自己尝试读代码望海涵 题一环形链表
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1 思路一 定义快慢指针slowfastslow每次走一步fast每次走两步假设到环口长度为L环的周长为Cslow从环口到相遇点为S如下图slow走了:LS fast走了:2*(LS)当slow到环口时fast已经走了n圈到相遇时n1所以fast到相遇时走了:Ln*CS 得出运算式L n*C-S结论一个指针从起点走一个从相遇点走他们会在入口点相遇。 struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow head;struct ListNode* fast head;struct ListNode* newnode head;//判断有没有相遇点while(fast fast-next){slow slow-next;fast fast-next-next;//找到相遇点if(slow fast){struct ListNode* node slow;//分别从起点和相遇点开始走while(node ! newnode){newnode newnode-next;node node-next;}return newnode;}}return NULL;
}
题二复制带随机指针的链表
给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。
返回复制链表的头节点。
示例 1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出[[7,null],[13,0],[11,4],[10,2],[1,0]] 思路一
第一步:在原链表的每一个之间开辟一块相同空间的copy将val和下一个的地址复制并改变cur-nextcopy
第二步因为每个原链表后面都有一个复制的copy链表所以copy- randon都可以指向自己复制的randon核心: copycur- randon-next
第三步将copy链表从原链表head上分离出来并将各自的节点接上。 struct Node* copyRandomList(struct Node* head) {struct Node* cur head;while(cur){struct Node* next cur-next;//开辟copy的节点struct Node* copy (struct Node*)malloc(sizeof(struct Node));//复制值copy-val cur-val;//插入copy-next next;cur-next copy;//向后走cur next;}cur head;while(cur){struct Node* copy cur-next;if(cur-random ! NULL){//copy的随机节点指向自己的随机节点copy-random cur-random-next;}else{copy-random NULL;}cur copy-next;}//分离链表struct Node* copyhead NULL;struct Node* copytail NULL;cur head;while(cur){struct Node* copy cur-next;struct Node* next copy-next;//分离copy链表if(copytail NULL){copyhead copytail copy;}else{copytail-next copy;copytail copytail-next;}//恢复原链表cur-next next;cur next;}return copyhead;
}
本人实力有限可能对一些地方解释的不够清晰可以自己尝试读代码望海涵
