【算法刷题指南】链表
链表常用技巧与操作
技巧
- 画图：直观且形象，便于理解
- 引入新的虚拟“头”结点：在算法题中，一般给的都是无头的单向链表，这种链表需要考虑很多的边界情况
- 便于处理边界情况
- 便于对链表操作
- 不要吝啬空间，大胆定义变量
- 快满双指针：判断链表是否有环、找链表中环的入口、找链表中倒数第n个节点
常见操作
- 创建新的节点
new - 尾插
- 头插
2.两数相加
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *cur1=l1,*cur2=l2;
ListNode *res=new ListNode(0);
ListNode *prev=res;
int t=0;
while(cur1||cur2||t)
{
if(cur1)
{
t+=cur1->val;
cur1=cur1->next;
}
if(cur2)
{
t+=cur2->val;
cur2=cur2->next;
}
prev->next=new ListNode(t%10);
prev=prev->next;
t/=10;
}
prev=res->next;
delete res;
return prev;
}
};24.两两交换链表中的节点
- 循环迭代（模拟）
- 定义变量，记录节点
- 实现两两节点交换即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==nullptr || head->next==nullptr) return head;
ListNode *newhead=new ListNode(0);
newhead->next=head;
ListNode *prev=newhead,*cur=prev->next,*next=cur->next,*nnext=next->next;
while(cur&&next)
{
prev->next=next;
next->next=cur;
cur->next=nnext;
prev=cur;
cur=nnext;
if(cur) next=cur->next;
if(next) nnext=next->next;
}
cur=newhead->next;
delete newhead;
return cur;
}
};143.重排链表
- 模拟
- 将链表一分为2，使用快慢指针找到分界点
- 合并两个链表即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
ListNode *slow=head,*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
ListNode *head2=new ListNode(0);
ListNode *cur=slow->next;
slow->next=nullptr;
while(cur)
{
ListNode *next=cur->next;
cur->next=head2->next;
head2->next=cur;
cur=next;
}
ListNode *ans=new ListNode(0);
ListNode *anscur=ans,*cur1=head,*cur2=head2->next;
while(cur1)
{
anscur->next=cur1;
cur1=cur1->next;
anscur=anscur->next;
if(cur2)
{
anscur->next=cur2;
cur2=cur2->next;
anscur=anscur->next;
}
}
delete head2;
delete ans;
}
};23.合并k个升序列表
- 优先队列小根堆
- 先建立小根堆，链表的头结点加入到小根堆中
- 创建一个新的链表，将小根堆中的对顶加入的新链表中，并且将该堆顶元素的下一个节点加入到小根堆中
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
struct cmp
{
bool operator()(ListNode* l1,ListNode *l2)
{
return l1->val > l2->val; //值较大的向下调整
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
//所有的头结点进入小根堆中
for(auto l:lists)
{
if(l) heap.push(l);
}
//合并
ListNode *ans=new ListNode(0);
ListNode *prev=ans;
while(!heap.empty())
{
ListNode* t=heap.top();
heap.pop();
prev->next=t;
prev=t;
if(t->next) heap.push(t->next);
}
prev=ans->next;
delete ans;
return prev;
}
};25.K个一组翻转链表
- 模拟
- 先求出需要逆序多少组：n
- 重复n次，长度为k的链表逆序即可，直接使用头插法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
int n=0;
ListNode *cur=head;
while(cur)
{
n++;
cur=cur->next;
}
n/=k;
ListNode *newhead=new ListNode(0);
cur=head;
ListNode *prev=newhead;
for(int i=0;i<n;i++)
{
ListNode *tmp=cur;
for(int j=0;j<k;j++)
{
ListNode *next=cur->next;
cur->next=prev->next;
prev->next=cur;
cur=next;
}
prev=tmp;
}
prev->next=cur;
cur=newhead->next;
delete newhead;
return cur;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-02-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
