网站建设与设计实训总结,石家庄最新新闻事件,网站建设投资预算,在线开发app的平台目录
1.返回倒数第K个节点【链接】
代码实现
2.链表的回文结构【链接】
代码实现
3.相交链表【链接】
代码实现
4.判断链表中是否有环【链接】
代码实现
常见问题解析
5.寻找环的入口点【链接】
代码实现1
代码实现2
6.随机链表的复制【链接】
代码实现 1.…目录
1.返回倒数第K个节点【链接】
代码实现
2.链表的回文结构【链接】
代码实现
3.相交链表【链接】
代码实现
4.判断链表中是否有环【链接】
代码实现
常见问题解析
5.寻找环的入口点【链接】
代码实现1
代码实现2
6.随机链表的复制【链接】
代码实现 1.返回倒数第K个节点【链接】 题目描述 实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。 思路快指针先走k步然后快指针和慢指针同时走直到快指针走到NULL此时慢指针的节点即为所求。 解析 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k){struct ListNode*fasthead,*slowhead; //快指针先走k步while(k--){fastfast-next;}//快慢指针一起走while(fast){slowslow-next;fastfast-next;}return slow-val;
}
2.链表的回文结构【链接】 题目描述 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。 给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 思路首先找到中间节点将中间节点后半部分倒置再分别从头结点和尾节点向中间遍历看对应值是否相等。 这里需要用到曾经写过的找链表的中间节点函数和反转链表函数可参照【单链表的应用】 代码实现
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {public:/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针struct ListNode* slow head;struct ListNode* fast head;//如果有两个中间节点则返回第二个中间节点while (fast fast-next) {slow slow-next;fast fast-next-next;}//此时slow刚好指向中间节点return slow;}struct ListNode* reverseList(struct ListNode* head) {// 重新创建一个链表将之前的链表进行头插即可struct ListNode* rphead nullptr;// 进行指针变换struct ListNode* cur head;while (cur ! nullptr) {// 用于保存下一个节点地址struct ListNode* newnode cur-next;// 头插cur-next rphead;rphead cur;cur newnode;}return rphead; //返回新链表的头rhead}bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);struct ListNode* rmid reverseList(mid);while (rmid A) {if (rmid-val ! A-val) {return false;}rmid rmid-next;A A-next;}return true;}
};
3.相交链表【链接】 题目描述 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 示例1相交节点不是1而是8注意这里不能比值因为两个不同节点的值可能一样要比较节点的地址。 思路1暴力求解对于链表A中的每个节点我们都遍历一次链表B看B中是否有相同节点第一个找到的就是第一个公共节点假设A链表有M个节点B链表有N个节点时间复杂度太高了为O(M*N)即O(N^2)。 思路2先判断两个链表是否相交可以通过判断两个链表最后一个节点地址是否相同如果尾节点相同说明两个链表一定相交如果不相等直接返回空指针。计算出两个链表的长度让长链表先走相差的长度然后让两个链表同时走直到遇到相同的节点就是第一个公共节点返回指向这个节点的指针。 解析 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curAheadA,*curBheadB;int lenA0,lenB0;while(curA-next){curAcurA-next; lenA; }while(curB-next){curBcurB-next; lenB; //此时B链表的长度少算一个}//尾节点不相等就是不相交if(curA!curB){return NULL;}lenA1;lenB1;//长的先走差距步再同时走第一个相等的就是交点//假设法int gapabs(lenA-lenB);//求绝对值struct ListNode *longListheadA,*shortListheadB;//longList指向长链表shprtList指向短链表//如果B比A长再修改一下指针的指向让longList指向长链表BshprtList指向短链表Aif(lenBlenA){longListheadB;shortListheadA;}while(gap--)//走差距步{longListlongList-next;}while(longList!shortList){longListlongList-next;shortListshortList-next;}return shortList;//返回哪一个都可以
}
4.判断链表中是否有环【链接】 题目描述 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 思路首先让快慢指针fast、slow指向链表的头节点head, 让快指针fast一次向后移动两个节点慢指针一次向后移动一个节点, 判断fast和slow是否走到同一个节点上数学上追击相遇问题如果走到同一个节点上就返回true。 代码实现
bool hasCycle(struct ListNode *head) {struct ListNode*slowhead,*fasthead;while(fastfast-next)//当一个链表中没有环时fast一定会移动到链表的结尾{slowslow-next;fastfast-next-next;if(slowfast){return true;}}return false;
}
常见问题解析 1.快慢指针为什么会相遇它们有没有可能错过永远追不上 不会错过。 假设slow进环时fast 和 slow 的距离是N追击过程中二者距离变化如下 N-N-1-N-2-……-3-2-1-0 每追击一次二者之间距离缩小1距离为0即相遇。 2.慢指针slow一次移动一个节点快指针一次移动多个节点3,4,5……n可行吗 可行。 用快指针一次移动3个节点举例 假设slow进环时fast 和 slow 的距离是N追击过程中二者距离变化如下 情况1N-N-2-N-4-……-4-2-0N为偶数 情况2N-N-2-N-4-……-5-3-1--1N为奇数N为-1表示错过了距离变成C-1C为环的长度 如果C-1是偶数新一轮追击就追上了如果C-1是奇数那么就永远追不上 如果N是奇数并且C是偶数那么就永远追不上那这种条件存在吗 假设slow进环前走的距离为L,设slow进环时fast已经在环中转了x圈 slow走的距离L fast走的距离Lx*CC-N 由fast走的距离是slow的三倍产生的数学等式3LLx*CC-N 化简得2L(x1)*C-N 我们发现偶数(x1)*偶数-奇数不成立反证出当N是奇数时C也一定是奇数。 总结一下一定能追上N是偶数第一轮就追上了N是奇数第一轮追不上C-1是偶数第二轮就追上了。 5.寻找环的入口点【链接】 题目描述 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 思路1用两个指针head、meet分别指向链表的头节点和快慢指针相遇的节点同时移动两个指针当两个指针指向同一个节点时该节点就是环的入口点 。 解析 假设环的长度为C到达相遇点时慢指针slow走过的距离为LN一圈之内肯定会被追上快指针fast走过的距离为Lx*CN 假设快指针走了x圈N一定大于等于1由fast走的距离是slow的2倍产生的数学等式2*(LN)Lx*CN 化简得Lx*C-N 也就是说head到入口点的距离等于meet指针转x圈减去N的距离head走到入口点meet也刚好走到入口点所以两个指针一起遍历最终会同时到达入口点。 代码实现1
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){struct ListNode *meetslow;while(meet!head){meetmeet-next;headhead-next;} return meet;}}return NULL;
} 思路2让快慢指针相遇节点与下一个节点断开然后将问题转化为两个链表的相交环的入口点其实就是两个链表的相交点。 解析 代码实现2 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curAheadA,*curBheadB;int lenA0,lenB0;while(curA-next){curAcurA-next; lenA; }while(curB-next){curBcurB-next; lenB; //此时B链表的长度少算一个}//尾节点不相等就是不相交if(curA!curB){return NULL;}lenA1;lenB1;//长的先走差距步再同时走第一个相等的就是交点//假设法int gapabs(lenA-lenB);//求绝对值struct ListNode *longListheadA,*shortListheadB;//longList指向长链表shprtList指向短链表//如果B比A长再修改一下指针的指向让longList指向长链表BshprtList指向短链表Aif(lenBlenA){longListheadB;shortListheadA;}while(gap--)//走差距步{longListlongList-next;}while(longList!shortList){longListlongList-next;shortListshortList-next;}return shortList;//返回哪一个都可以
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){struct ListNode *meetslow;struct ListNode *newheadmeet-next;meet-nextNULL; return getIntersectionNode(head,newhead);}}return NULL;
}
6.随机链表的复制【链接】 题目描述 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 深拷贝就是拷贝一个值和指针指向都跟当前链表一模一样的链表。 思路: 拷贝节点到原节点的后面再寻找途径处理random指针处理完后对复制的节点拿下来尾插成新链表返回新链表的头。 解析 代码实现
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*///拷贝节点插入在原节点的后面
struct Node* copyRandomList(struct Node* head) {struct Node*curhead;while(cur){struct Node*copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;copy-nextcur-next;//注意这里顺序不能颠倒cur-nextcopy;curcopy-next;}//控制randomcurhead;while(cur){struct Node*copycur-next;if(cur-randomNULL){copy-randomNULL;}else { copy-randomcur-random-next;}curcopy-next; }//把拷贝节点取下来尾插成为新链表然后恢复原链表struct ListNode*copyheadNULL,*copytailNULL;curhead;while(cur){struct ListNode*copycur-next;struct ListNode*nextcopy-next;if(copytailNULL){copyheadcopytailcopy;}else{copytail-nextcopy;copytailcopytail-next;}cur-nextnext;//恢复原链表有没有这句代码都行curnext;}return copyhead;
}
