当前位置：首页 > news >正文

链表OJ经典题目及思路总结（二）头结点

news 2025/6/30 10:55:54

系列文章目录

链表OJ经典题目及思路总结（一）双指针
链表OJ经典题目及思路总结（二）头结点

文章目录

系列文章目录
前言
1.建立新链表
- 1.1 移除链表元素
2.哨兵位的头结点
- 2.1 链表分割
- 2.2 合并两个有序链表
3.CV工程师
总结

前言

对于题目的理解是非常重要的，对于解题思路的训练也很重要，对于思维的打磨也很重要，今天我们来看经典的OJ题目，以及两大思想：创建新链表进行操作，尽量不要改动原链表；同时，哨兵位的头结点，可以减少一些麻烦，今天的题主要是无需对空链表进行考虑，也即无需单独处理第一个结点（可能为空节点）。

1.建立新链表

1.1 移除链表元素

203.移除链表元素（题目链接）
在这里插入图片描述
思路1：遍历链表，删除数据域为val的结点；
思路2：将值不为val的节点尾插到新的链表中，返回新链表的头结点（头指针）。

注意：两种思路整体都是遍历原链表，但是有几个坑！

坑点1：如果尾插第一个结点，要更改新的头指针newhead；但后续插入不需要再更改头指针。
坑点2：如果最后一个结点的值不是val，那么将其尾插到新链表，其next指针域为NULL；但是如果最后一个结点的值是val，其前一个结点（假设prev指向该结点）被尾插到新链表，prev->next指向的最后一个节点（数据域为val）被free，那么prev->next是野指针，所以要将其置为NULL.

比如下图中当数据域为5的结点被尾插到新链表之后，tail指向该节点，tail->next=p，但是free§之后，p就是野指针了，应将tail->next手动置为NULL.
在这里插入图片描述

坑点3：第二点和链表本身为空可以合在一起考虑，如果head为NULL，那么cur为NULL，遍历原链表的while循环不会执行，tail为NULL，newhead为NULL，直接返回即可；而如果tail不为NULL，tail->next有可能为NULL，不考虑太多，直接置为NULL.

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/ 
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur=head, *newhead=NULL, *tail=NULL;//cur用于遍历要删除的链表//newhead用于存放要新链表的头指针，用于返回//tail用于尾插，否则每次尾插都要遍历新链表找尾节点，效率不高while(cur)//while循环遍历要删除的链表{//结点数据域为val与非val分开处理，val则删除，非val则尾插到新链表if(cur->val!=val){//插入第一个元素和后续元素不同的是，插入第一个元素需要更改头指针，要单独处理//坑点1 if(tail==NULL)newhead=tail=cur;else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{struct ListNode* next=cur->next;free(cur);cur=next;}}//坑点2,3if(tail)tail->next=NULL;return newhead;
}

2.哨兵位的头结点

2.1 链表分割

CM11 链表分割（题目链接）
在这里插入图片描述
或许有一些小伙伴的思路是，将大于等于x的结点删除同时尾插到原链表。这种思路的问题是：

首先不推荐在链表中间进行插入和删除，因为要记录前一个节点的位置，防止链表后续节点丢失；
其次，将大于等于x的结点不断插入到链表，要先遍历链表找到尾结点，不然会导致大于等于x的结点被循环插入，没有终止。并且还要再次遍历链表进行删除、尾插，这样就遍历了两次链表，效率下降不高；
第三，这种同时进行删除、尾插的行为对代码、逻辑思维能力要求较高，一不小心，无论是调试还是修改都容易凌乱。

因此无论是移除链表元素还是链表分割，我们都推荐将结点插入到新链表！

对于该题，遍历原链表，将值小于x的结点尾插到一个新链表，值大于等于x的结点尾插到另一个新链表，最后将两个链表链接，因为尾插不改变原来结点的相对顺序。

这里引入一个哨兵位的头结点，因为尾插要判断链表是否为空，如果为空，就要单独处理。哨兵位的头结点一般都是动态申请，用完进行free（牛客链接可能测不出内存泄漏问题）。

并且两个新的用于插入的链表都引入头结点，这样，即使传入的链表为空也无需单独讨论；即使链表所有结点数据域的值都大于等于或都小于x，也无需进行单独处理。

代码示例如下

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include <asm-generic/errno.h>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* cur=pHead;struct ListNode* greatGuard,*greatTail,*shortGuard,*shortTail;//动态申请头结点greatGuard=greatTail=(struct ListNode*)malloc(sizeof(struct ListNode));shortGuard=shortTail=(struct ListNode*)malloc(sizeof(struct ListNode));greatGuard->next=shortGuard->next=NULL;while(cur){if(cur->val<x){//尾插shortTail->next=cur;shortTail=shortTail->next;}else {greatTail->next=cur;greatTail=greatTail->next;}cur=cur->next;}//链接shortTail->next=greatGuard->next;//这个地方greatTail是原来的cur赋值得来的，所以greatTail可能还存储着原链表的下一个节点的地址，具体如下图，所以要将greatTail->next置为NULL.greatTail->next=NULL;pHead=shortGuard->next;free(greatGuard);free(shortGuard);   return pHead;}
};

下图示例中，两个链表链接后数据域为2的结点指向数据域为4的结点，数据域为7的结点next指针域存储数据域为1的结点的地址，最后会循环遍历1 3 2 4 6 7 1 3 2 4 6 7…链表成了循环单链表，与题目不符。
在这里插入图片描述

2.2 合并两个有序链表

21.合并两个有序链表（题目链接）
在这里插入图片描述
思路：
注意建立新链表，而不是在原链表进行操作以及哨兵位的头结点可以减少很多麻烦；
双指针分别遍历两个链表，并比较结点的值，将值较小的链表尾插到新链表；
哨兵位的头结点可以避免尾插检查链表是否为空的问题。
代码实现如下

/*** 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,*guard=NULL,*tail=NULL;guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));tail->next=NULL;while(cur1 && cur2){if(cur1->val<cur2->val){tail->next=cur1;tail=tail->next;cur1=cur1->next;}else{tail->next=cur2;tail=tail->next;cur2=cur2->next;}}if(cur1)tail->next=cur1;if(cur2)tail->next=cur2;struct ListNode* head=guard->next;free(guard);return head;
}

如果没有头结点，代码如下，每次头插都要考虑链表是否为NULL.

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL && list2==NULL)return false;struct ListNode* cur1=list1,*cur2=list2,*newhead=NULL,*tail=NULL;while(cur1 && cur2){if(cur1->val<cur2->val){if(newhead==NULL)newhead=tail=cur1;else{tail->next=cur1;tail=tail->next;}cur1=cur1->next;}else{if(newhead==NULL)newhead=tail=cur2;else{tail->next=cur2;tail=tail->next;}cur2=cur2->next;}}  if(cur1){if(newhead==NULL)newhead=cur1;elsetail->next=cur1;}  if(cur2){if(newhead==NULL)newhead=cur2;elsetail->next=cur2;}return newhead;
}

以上两个代码均通过测试，我们看到，不带头结点代码要考虑得多，且较为繁琐。

3.CV工程师

OR36 链表的回文结构（题目链接）
在这里插入图片描述
思路：一共有两种可能情况，第一种，一共偶数个元素，将中间结点及其后面的结点反转后与前半部分剩余的结点完全一致；
第二种，一共奇数个元素，将中间结点及其后面的结点翻转后比前半部分剩余的结点多一个，但是，我们可以看到下图中的指向关系，前半部分的2结点指向3结点，反转后指向不变，遍历head链表用于比较。

反转后的头指针为rhead，将rhead与head所指的链表进行比较，当rhead为NULL时停止。

在这里插入图片描述
所以要找中间结点，并且反转链表，找到我们之前写的反转链表和找链表中间结点的代码，Ctrl+C，Ctrl+V即可，做CV工程师~

反转链表和找链表中间结点的代码在系列文章中，下面为链接，有兴趣的友友可以看一下。
链表OJ经典题目及思路总结（一）双指针

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {public:struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast = head, *slow = head;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;}return slow;}struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head, *newhead = NULL;while (cur) {struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}bool chkPalindrome(ListNode* head) {// write code herestruct ListNode* mid= middleNode(head);struct ListNode* rhead = reverseList(mid);while(rhead){if(rhead->val != head->val)return false;rhead=rhead->next;head=head->next;}return true;}
};