沈阳制作网站,网站建设代理政策,做墙绘一般在哪个网站,wordpress 预约系统链表算法 前言一.原地逆置思路一#xff1a;头插法思路二#xff1a;双指针法思路3#xff1a;递归 例题#xff1a;1.头插法2.双指针法3#xff0c;递归 二.双指针快慢指针#xff1a;一个指针快一个指针慢例题1例题2 前言 我会将一些常用的算法以及对应的题单给写完头插法思路二双指针法思路3递归 例题1.头插法2.双指针法3递归 二.双指针快慢指针一个指针快一个指针慢例题1例题2 前言 我会将一些常用的算法以及对应的题单给写完形成一套完整的算法体系以及大量的各个难度的题目目前算法也写了几篇题单正在更新其他的也会陆陆续续的更新希望大家点赞收藏我会尽快更新的 一.原地逆置
思路一头插法 若带头节点先将头节点摘下来 然后从第一个节点开始挨个插入每一个节点 摘下来后用头插法建立新的链表 思路二双指针法 定义两个指针pre和curpre在前cur在后 每次让pre的next指向cur实现一次局部反转 局部反转之后。pre和cur同时往后移动一个位置循环上述过程直至pre到达链表尾部在循环过程中需要记录pre-next 思路3递归 递归出口传进来的节点p的next NULL 递归体递归调用把p之后的先反转 例题
力扣206. 反转链表
1.头插法
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///头插法
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* p head;if(head NULL){//先判断是否为空return NULL;}struct ListNode* q p-next;head NULL;//将节点从链表拿下来while(q ! NULL){p-next head;head p;p q;q q-next;}p-next head;return p;
}2.双指针法
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///双指针法
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* p head;//指向头节点struct ListNode* q NULL;//指向头节点的上一个节点while(p ! NULL){//struct ListNode* t p-next;//保存p-nextp-next q;q p;p t;}return q;
}3递归
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///递归
struct ListNode* reverse (struct ListNode* cur, struct ListNode* pre);struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur head;struct ListNode* pre NULL;return reverse (cur, pre);
}struct ListNode* reverse (struct ListNode* cur, struct ListNode* pre){if (cur NULL) {return pre;}else {struct ListNode* tmp cur - next;cur - next pre;return reverse (tmp, cur);}
}二.双指针
快慢指针一个指针快一个指针慢
例题1
力扣LCR 140. 训练计划 II
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {struct ListNode* cur head;struct ListNode* next head;for(int i 0; i cnt; i){next next-next;}while(next){cur cur-next;next next-next;}return cur;
}例题2
力扣142. 环形链表 II 找环开始节点慢指针每次走一个节点快指针每次走两个节点当相遇时再来一个指针从头一个一个走。当与慢指针相遇的时候为开始节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {if(head NULL || head-next NULL || head-next-next NULL){return NULL;}struct ListNode* s head;struct ListNode* f head;while(f ! NULL){s s-next;if(f-next NULL){return NULL;}f f-next-next;if(f s){struct ListNode* t head;while(t ! s){t t-next;s s-next;}return t;}}return NULL;}未完待续……
