好题分享（2023.11.5——2023.11.11）

编程入门行业动态更新时间:2024-10-24 23:26:51

前情回顾：

前言：

题目一：补充《移除链表元素》

题目二：《反转链表》

解法一：三指针法

解法二：头插法

题目三：《相交链表》

题目四：《合并两个有序数列》

题目五：《链表中倒数第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(tail==NULL){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(head==NULL){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(cur1==NULL){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(n<=0 && 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->val<x){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(L+X) = L + X + n*C

假设这个环足够小，那么我的fast很有可能在圆环内走很多圈，但我们假设就走过一圈。

则就有以下算式：

2(L+X) =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;
}

本道题目较难，我在这里先讲解以下思路：