做网站是学什么编程语言,WordPress cdn缓存哪些,怎么在中国移动做网站备案,网站建设服务流程目录
前情回顾#xff1a;
前言#xff1a;
题目一#xff1a;补充《移除链表元素》
题目二#xff1a;《反转链表》
解法一#xff1a;三指针法
解法二#xff1a;头插法
题目三#xff1a; 《相交链表》
题目四#xff1a;《合并两个有序数列》
题目五
前言
题目一补充《移除链表元素》
题目二《反转链表》
解法一三指针法
解法二头插法
题目三 《相交链表》
题目四《合并两个有序数列》
题目五《链表中倒数第K个节点》
题目六《链表的分割》
题目七《链表的回文结构》
题目八《环形链表一》 题目九《环形链表二》
由题目八引出结论
对于第九题的算法
总结
题目十《随机链表的复制》
1.先拷贝各个节点再连接起来
2.对random进行赋值
3.断开连接
总结 前情回顾
我们在上一篇好题分析中分析了以下几题
《合并两个有序数组》《移除链表元素》《链表的中间节点》
上一篇的好题分析的blog在
好题分析2023.10.29——2023.11.04-CSDN博客
前言
本次好题分享我们将对《移除链表元素》进行一种算法即思路进行补充因为在之后的题目都是围绕此算法来实现的
同时我们还将对Leecode和牛客网上的众多题目进行分析
《反转链表》《相交链表》《环形链表一》《环形链表二》《随机链表的复制》《合并两个有序链表》
《链表中倒数第K个节点》《链表分割》《链表的回文结构》
题目一补充《移除链表元素》 力扣LeetCode官网 - 全球极客挚爱的技术成长平台
我们在上一篇blog中我们是利用三个指针来进行操作在删除节点前保存该节点前后的节点再进行修改指向的操作此算法的不足之处就在于如果我们要删除的元素位于头结点那么这个时候就要考虑另外一种情况了。
接下来的算法将可以省去上述步骤且在之后的刷题中会更高效 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///创建“新链表”
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newhead NULL,*cur head,*tail NULL;while(cur){//不是val节点的拿下来尾插if(cur-val ! val){//尾插if(tailNULL){newhead tail cur;}else{tail-next cur;tail tail-next;}cur cur-next;}else{cur cur-next;}}if(tail){tail-next NULL;}return newhead;
} 该算法是先创建一个新链表将需要的节点连接到新链表中再返回新创建的指针。
刚开始由于newnode指向的是NULL即该链表为空所以我们需要进行尾插操作同时tail也指向新链表的第一个节点。
即
但是要注意的是此时我们newnode中的头结点它的next是指向原链表中所在位置的下一个节点的并非指向NULL即
你可能会觉得代码中该部分是多余的
但是这一步缺失这种算法的关键。
如果我们这时候的cur指向了题目描述中的val此时cur就会跳过该节点。
并指向下一个节点那么如果没有tail-next cur这一行代码
那么新链表中的tail将直接指向题目描述中的val。
所以我们必须加上此代码 当遇到此时的情况时如果我们直接放回newnode就会是一个不完整的链表因为尾结点并没有指向NULL所有我们务必要在最后加上一句tail-next NULL; 这种创建新链表的思想需要我们去学习在之后的题目中尤为重要
题目二《反转链表》
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
对于本题目我将给出两种算法为了展示出创建新链表该种算法的优势。
解法一三指针法 如果我们尝试常规解法来实现那我们我们就务必需要保存前后节点的位置。
所以该算法实现 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///三指针法
struct ListNode* reverseList(struct ListNode* head) {if(headNULL){return NULL;}struct ListNode* n1 NULL,*n2 head,*n3 head-next;if(n3 NULL){return n2;}while(n2 ! NULL){n2-next n1;n1 n2;n2 n3;if(n3)n3 n3-next;}return n1;
}
这道题还要注意如果链表只要一个节点或者无节点时的返回值
解法二头插法 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///头插法
struct ListNode* reverseList(struct ListNode* head) {if(head NULL){return NULL;}struct ListNode* newnode NULL;struct ListNode* cur head;struct ListNode* next head-next;while(next){cur-next newnode;newnode cur;cur next;next next-next;}cur - next newnode;newnode cur;return newnode; }
反转的本质就是在新链表中头插 。
那么我们就可以将cur-next指向newnode;
newnode再指向此时的cur这就完成了头插操作
再将cur next
next next - next;
因为我们改变来cur-next的指向所以我们对于保存cur下一个节点的位置就尤为重要
完成操作后我们最好可以将head NULL避免出现野指针。
题目三 《相交链表》
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA headA, *curB headB;int countA 0;int countB 0;//判断是否相交while(curA-next){curA curA-next;countA;} while(curB-next){curB curB-next;countB;} if(curA ! curB){return NULL;}//找出相交的起始节点int n abs(countA - countB);if(countA countB){while(n){headA headA-next;--n;}while(headA ! headB){headA headA-next;headB headB-next;}return headA;}else{while(n){headB headB-next;--n;}while(headA ! headB){headA headA-next;headB headB-next;}return headB;}} 对于该题目我们提供一种算法
1.先判断它们是否相交。
2.找到第一个公共节点。
相交好判断
我们可以先遍历找到它们最后一个节点如果节点相同就说明它们相交
因为相交链表只能是“Y”型相交而绝对不可能是“X”型的
那么对于第二步
我们可以先求出两个链表分别有多长再相减求绝对值得出相差步。
再使得短的链表的curA先走相差步这样两个指针就是从同一位置起步了
再一起同时走一步直到它们相等如果这时两指针相等则就说明相等的节点就是第一个公共节点
让curB走向差步
在同时走一步
如此就可以得到公共节点 题目四《合并两个有序数列》 力扣LeetCode官网 - 全球极客挚爱的技术成长平台
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1 list1,*cur2 list2;struct ListNode* newnode (struct ListNode*)malloc(sizeof(struct ListNode));newnode-next NULL;struct ListNode* next NULL;struct ListNode* tail newnode;while(cur1 cur2){if((cur1-val cur2-val)){next cur1-next;tail-next cur1;cur1 next;tail tail-next;}else{next cur2-next;tail-next cur2;cur2 next;tail tail-next;}}if(cur1NULL){tail-next cur2;}else{tail-next cur1;}return newnode-next;
} 对于该题目我建议使用新链表法同时我们最好创建一个哨兵位的头结点。
具体为什么我这里建议使用新链表法想要反驳的同学下去可以自己动手创建一个无哨兵位的解法相信你一定会被绕晕的。
鉴于我们已经学会了前面两道题目的算法这道题相信大家一定很好理解
如此循环当cur1或者cur2为NULL时则直接让tail-next指向cur1或cur2.
即
题目五《链表中倒数第K个节点》 链表中倒数第k个结点_牛客题霸_牛客网 /*** struct ListNode {* int val;* struct ListNode *next;* };*//*** * param pListHead ListNode类 * param k int整型 * return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code hereif(pListHead NULL){return NULL;}int count 0;struct ListNode* tmp pListHead;while(tmp){count;tmp tmp-next;}int n count - k;if(n0 k count){return NULL;}while(n--){pListHead pListHead-next;}return pListHead;} 该题目的算法实现还是好理解
我们先统计该链表存在多少个节点。
然后再减去所谓的倒数第K个。
就可以得到正数第几个n
再将pListHead进行遍历同时n--
再返回此时的pListHead
思路还是好理解的在这里我就不进行画图展示了。
题目六《链表的分割》
链表分割_牛客题霸_牛客网
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include cstddef
class Partition {
public:ListNode* partition(ListNode* pHead, int x){// write code herestruct ListNode* head1,*tail1,*head2,*tail2;head1 tail1 (struct ListNode*)malloc(sizeof(struct ListNode));head2 tail2 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur pHead;while(cur){if(cur-valx){tail1-next cur;tail1 tail1-next;}else {tail2-next cur;tail2 tail2-next;}cur cur-next;}tail1-next head2-next;//防止成环tail2-next NULL;pHead head1-next;free(head1);free(head2);return pHead;}
}; 对于该题目的算法思路要注意的有以下几点
1.我们在此选择开辟两个哨兵位的头节点创建链表小于等于x的到第一个链表大于x的到第二个链表。
2.再将小链表的最后一个节点的next链接到第二个哨兵位头节点的next。
3.同时还要注意成环问题
如此一直循环
到这里时我们就可以直接将tail1-next head2-next;
即
此时一定不要忘记将tail2-next NULL
因为此时的tail2-next是指向的tail1指向的节点的
如果这里不注意的话就会形成一个环
如此才是正确的全部思路。 题目七《链表的回文结构》
链表的回文结构_牛客题霸_牛客网 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code here//找中间节点ListNode* fast A;ListNode* slow A;while(fast fast-next){fast fast-next-next;slow slow-next;}//逆序ListNode* next slow -next;ListNode* rehead slow;rehead-next NULL;while(next){slow next;next slow-next;slow-next rehead;rehead slow;}while(A rehead){if(A-val rehead-val){A A-next;rehead rehead-next;}else{return false;}}return true;}
}; 由于牛客网对于本题目只要C一种格式但是没关系C兼容C语言。
所有我们就按照我们的写法即可
第一步利用快慢指针找到中间节点
即
此时的该节点就为中间节点。
再逆序中间节点后面的全部节点
利用新链表法
先创建个指针rehead
在创建的时候提前将slow指向的节点拿下来进行置空操作即
再进行一个经典的头插操作即while循环里面的全部操作
如此就可以进行全部逆序的操作则此时的图为
我们只需要分别将A和rehead每次挪动一步再判断是否为相等即可。
如果一直相等直到循环结束就return true
如果出现不想等的直接return false 题目八《环形链表一》 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* fast,*slow;fast slow head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){return true;}}return false;
}
对于一个带环链表我们遇到该种题目应当先考虑考虑快慢指针算法。
如图 fast一次走两步slow一次走一步当它们相遇的时候一定是在圆环内
例 从上述可以看出再进行第三次循环的时候fast和slow就相遇就说明此时的链表是带环链表。 题目九《环形链表二》
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast head, *slow head;struct ListNode* meet NULL;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){meet slow;while(head ! meet){head head-next;meet meet-next;}return head;}}return NULL;
}
这道题与上题类似但区别在于现在已经告诉你这是一个环形链表需要你求出进入环的第一个节点。
对于解决该问题的方法此方法偏向于数学思维思路。
我们由图来分析。
由题目八引出结论 我们在题目八中分析过如果我们利用快慢指针就可以求出它们是否再圆环内。
但是当快指针一次走三步呢
那么还可以追上吗
这就不得不利用数学思维来解决此问题。 我们可以将链表抽象为如图内容。
那么当fast一次三步时怎么判断它们是否相遇 当slow刚进入环内时fast肯定比slow快3倍走过的距离肯定也多三倍。
但是一旦它们都在环内时距离就会一直-2.
假设一开始的距离为n 此时的-1就代表了它们的距离相差1意思就是 那么就不难的出以下结论
假设C为圆的周长此时它们距离就是C-1。
如果C-1为偶数那么随着它们-2的操作最后会相遇。
但如果C-1是奇数那么随着它们-2的操作最后还需要再来一圈才可以相遇
即
1.若n为偶数直接就可以追上
2.若n是奇数C是奇数得过两圈才能追上。
3.如果n是奇数C是偶数永远都追不上。 但是第3条是不成立的因为我们可以得出公式 L为直线长 N是两指针在刚开始的距离 3L L n*C - N 即2L n*C - N 等号左边百分百为偶数 而右边永远等于奇数。 所以它们不相等即该结论永远不成立 对于第九题的算法 而对于该题目我们只需要知道此时的fast只走一步而它们绝对可以在圆环内相遇 我们在它们相遇的地方创建个指针指向该地方后面我们就会用到此指针 我们在创建个未知数X代表第一个环节点到相遇点 通过该图我们可以知道slow走过的路程 fast的路程/2
所以就有2(LX) L X n*C
假设这个环足够小那么我的fast很有可能在圆环内走很多圈但我们假设就走过一圈。
则就有以下算式
2(LX) L X C
L C - X
通过以上的推导
我们知道了以下 L Y 那我们就可以让meet和head同时走一步直到它们相遇因为相遇的地方就是圆环的第一个节点。 这样就可以求出来第一个节点了
总结
本题目设计到的数学思维和思路会使很多同学绕不清楚还有转不过弯来。
对于这部分的解法下来需要好好熟练掌握并学习学习在这里我就不再多讲了。
题目十《随机链表的复制》 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {if (head NULL) {return NULL;}struct Node* cur head;struct Node* copy NULL;while(cur){copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;copy-next cur-next;cur-next copy;cur cur-next-next;}copy head-next;struct Node* tmp NULL;cur head;while(cur){tmp cur-next;tmp-random (cur-random ! NULL)?cur-random-next : NULL;cur cur-next-next;}tmp copy;while(tmp-next ! NULL){tmp-next tmp-next-next;tmp tmp-next;}return copy;
}
本道题目较难我在这里先讲解以下思路
1.先拷贝各个节点再连接起来 2.对random进行赋值 这里格外要注意如果此时原radom是NULL就要另外讨论。
如果不为空则将cur-radom-next赋给copy
这一句代码则是精华所在
3.断开连接 将拷贝好的各个节点互相链接并且返回。
总结
本周的好题分享设计到的知识面较广我们在做题过程中难免会遇到一些难以实现的操作但是只要我们沉下心来一点点的了解和学习相信一定会有进步
记住“坐而言不如起而行”
Action speak louder than words!
