什么是链表？直观地通过代码解析如下（注意链表在cpp中不是一个预定义的数据类型，为此需要自己定义～）：
//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) {}
};
1. 合并两个有序链表
原本我的解法是用递归去做的，对应的复杂度是O(n+m)
/**
* 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 calulate(ListNode* list1, ListNode* list2,ListNode* &result_list)//注意输入的用指针的引用
{
if(list1==nullptr && list2==nullptr)
{
result_list=nullptr;//置空
return;//直到两个都为空的时候，就返回
}
else if(list1!=nullptr && list2!=nullptr)//两个都不为空
{
if(list1->val<=list2->val)
{
result_list->val=list1->val;
list1=list1->next;//迭代到下一个指针
}
else
{
result_list->val=list2->val;
list2=list2->next;
}
result_list->next = new ListNode();// 初始化 result_list->next 以防止空指针访问
calulate(list1, list2, result_list->next);
}
else if(list1==nullptr || list2==nullptr)//若两者有一个为空
{
ListNode *no_empty= (list1==nullptr? list2: list1);//非空的一个
result_list=no_empty;//直接等于非空的一个~
return;//返回
}
}
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 采用递归的方法去解决
ListNode* result_list=new ListNode(0);//初始化为0，为一个指针，指针的初始化为new
calulate(list1, list2,result_list);
return result_list;
}
};
此处改为采用双指针去解。时间复杂度应该是一样的，但是空间复杂度不一样。上面的递归的空间复杂度为O(n+m)。递归调用函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。
而用双指针来解题，空间复杂度为O(1)。因为只需要常数的空间来存放若干变量。
理解过程如下动图所示：
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 创建一个空的链表作为输出（此处采用的是虚拟头节点）
ListNode* result=new ListNode(0);//第一个是占位符，头节点不要，返回的为result->next
ListNode* p=result;//创建指向这个链表的指针
// 创建分别指向两个链表的指针
ListNode* p1=list1;
ListNode* p2=list2;
while(p1!=nullptr && p2!=nullptr)
{
if(p1->val < p2->val)//若p1当前的值小于p2,赋值p1
{
p->next=p1;//永远都是放到next中，这样就可以避免下一次访问空指针
p1=p1->next;//p1继续递推
}
else//若p1当前的值大于p2，赋值p2
{
p->next=p2;
p2=p2->next;//p2继续递推
}
p=p->next;//p也继续递推
}
if(p1!=nullptr)//若1还没结束，接到末尾
{
p->next=p1;
}
if(p2!=nullptr)//若2还没结束。接到末尾
{
p->next=p2;
}
return result->next;//注意返回的为除第一个以外的
}
};
注意上面解法返回的是result->next。采用的是「虚拟头结点」。
另外一种解法可以直接返回result，但是不采用虚拟头节点的话就要额外处理指针 p 为空的情况：
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1==nullptr && list2==nullptr)
return list1;
// 创建一个空的链表作为输出
ListNode* result=new ListNode(0);
ListNode* p=result;//创建指向这个链表的指针
// 创建分别指向两个链表的指针
ListNode* p1=list1;
ListNode* p2=list2;
while(p1!=nullptr && p2!=nullptr)
{
if(p1->val < p2->val)//若p1当前的值小于p2,赋值p1
{
p->val=p1->val;
p1=p1->next;//p1继续递推
}
else//若p1当前的值大于p2，赋值p2
{
p->val=p2->val;
p2=p2->next;//p2继续递推
}
p->next=new ListNode();// 初始化 以防止空指针访问
p=p->next;//p也继续递推
}
if(p1!=nullptr || p2!=nullptr)//若有没空的，接到末尾
{
ListNode *no_empty= (p1==nullptr? p2: p1);//非空的一个
p->val=no_empty->val;
p->next=no_empty->next;
}
return result;
}
};
2. 分隔链表
看到这道题的时候，第一个解决思路如下。将原链表一分为2，然后把大的链表放在小的链表后。通过两个链表，一个用来存放小于阈值的，另外一个用来存放大于阈值的。最后再把两个链表合并起来。
注意需要p_bigger->next = nullptr;来处理尾节点，避免循环引用。由于当前节点p_bigger复用的是原链表head的节点，而其 next 指针可能指向一个小于 x 的节点，需要切断这个引用。
时间复杂度为O（n），空间复杂度为O（1）
/**
* 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* partition(ListNode* head, int x) {
ListNode* result=new ListNode(0);//result->next就为结果
ListNode* p_result=result;//指结果的指针
ListNode* bigger=new ListNode(0);//bigger->next（存放大于目标值的链表）
ListNode* p_bigger=bigger;//指向存放大于等于目标值的链表
while(head!=nullptr)//一直遍历直到最后
{
if(head->val<x)
{
p_result->next=head;
p_result=p_result->next;//继续递推
}
else//就是大于等于值x的（可以理解为将大于等于目标值的放在新指针上，最后再放到结果中）
{
p_bigger->next=head;
p_bigger=p_bigger->next;//继续递推
}
head=head->next;//一直递推
}
p_bigger->next = nullptr; // 处理尾节点，避免循环引用
//最后再把bigger->next原来的链表中
if(bigger->next!=nullptr)
{
p_result->next=bigger->next;
}
return result->next;
}
};
下面解法则是直接在循环的时候就断开原链表的每个节点的next指针。
原因是采用的是链表赋值，那么原来的链表的next指针可能就继续指向其他节点，这样就很容易形成类似环路的结构。所以在赋值的时候，需要把原链表的每个节点的next指针断开，置为空。 （PS：若通过val关键字赋值，而不是用next指针赋值，那也可以解决）
总的来说，如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的。但凡遇到这种情况，就把原链表的节点断开，这样就不会出错了。
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* result=new ListNode(0);//result->next就为结果
ListNode* p_result=result;//指结果的指针
ListNode* bigger=new ListNode(0);//bigger->next（存放大于目标值的链表）
ListNode* p_bigger=bigger;//指向存放大于等于目标值的链表
while(head!=nullptr)//一直遍历直到最后
{
if(head->val<x)
{
p_result->next=head;
p_result=p_result->next;//继续递推
}
else//就是大于等于值x的
{
p_bigger->next=head;
p_bigger=p_bigger->next;//继续递推
}
// head=head->next;//原链表一直递推
// 断开原链表的每个节点的next指针
ListNode *temp = head->next;
head->next=nullptr;//把原链表的每个节点的next指针断开，置为空
head=temp;
}
//最后再把bigger->next原来的链表中（链接两个链表）
if(bigger->next!=nullptr)
{
p_result->next=bigger->next;
}
return result->next;
}
};
下面就是上面提到的，通过new ListNode来给指针赋值，那么就不需要每次额外断掉
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* result=new ListNode(0);//result->next就为结果
ListNode* p_result=result;//指结果的指针
ListNode* bigger=new ListNode(0);//bigger->next（存放大于目标值的链表）
ListNode* p_bigger=bigger;//指向存放大于目标值的链表
while(head!=nullptr)//一直遍历直到最后
{
if(head->val<x)
{
p_result->next=new ListNode(head->val);
p_result=p_result->next;//继续递推
}
else//就是大于等于值x的
{
p_bigger->next=new ListNode(head->val);
p_bigger=p_bigger->next;//继续递推
}
head=head->next;//原链表一直递推
}
//最后再把bigger->next原来的链表中
if(bigger->next!=nullptr)
{
p_result->next=bigger->next;
}
return result->next;
}
};
3. 合并 k 个有序链表
第一眼最基本的解法就是遍历(递归)用两两合并的方式。对于vector长度为k，每个链表最长的长度为n。第一次合并后，长度为n，第二次合并后为2n。第三次为3n，依次类推O（（1+k）k/2n）那么就是O（k2n）。空间复杂度为O（1）.
class Solution {
public:
ListNode* mergeTwoLists(ListNode* lists1, ListNode* lists2)
{
ListNode* result=new ListNode(0);
ListNode* p=result;//指向结果的指针
ListNode* p1=lists1;
ListNode* p2=lists2;
while(p1!=nullptr && p2!=nullptr)
{
if(p1->val<p2->val)
{
p->next=p1;
p1=p1->next;
}
else
{
p->next=p2;
p2=p2->next;
}
p=p->next;
}
if(p1!=nullptr || p2!=nullptr)
{
ListNode* no_empty=(p1!=nullptr)? p1:p2;
p->next=no_empty;
}
return result->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
//最直接的方法就是把它分解为多个两个链表的合并
// 时间复杂度应该是O（n^2）,空间复杂度还是O（1）
ListNode* result=nullptr;//初始化为空
for(int i=0;i<lists.size();i++)
{
result=mergeTwoLists(result, lists[i]);
}
return result;
}
};
更优的解法则是采用优先队列的思路，从k个链表的头节点的指针中来找最小的放入。
优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)。
所有的链表节点都会被加入和弹出 pq，所以算法整体时间复杂度是O(n*logk)。空间复杂度则由于用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)
下面是优先级队列的解法(关于优先队列请见参考资料，可以理解为本身在优先级队列中进行了排序了只是把结果存出来而已～):
class Solution {
public:
// 自定义比较器
struct Function_comparison {
bool operator()(ListNode* list1, ListNode* list2) {
return list1->val > list2->val; // 小顶堆
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 采用优先队列
priority_queue<ListNode*, vector<ListNode*>, Function_comparison> pq_group;
for(auto listnode:lists)
if (listnode!=nullptr)//要不为空才push
pq_group.push(listnode);//当前只是把节点头放进去而已
ListNode* result=new ListNode(0);//定义虚拟节点头
ListNode* p_result=result;//指针指向虚拟节点头
while(!pq_group.empty())//当队列不为空
{
ListNode* smallest_node=pq_group.top();//拿到第一个节点
pq_group.pop();//头个元素弹出
p_result->next=smallest_node;//赋值
if(smallest_node->next!=nullptr)//若不为空，则加到队列中
{
pq_group.push(smallest_node->next);
}
p_result=p_result->next;
}
return result->next;
}
};
采用lambda表达式的做法：
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 采用优先队列
//改为用Lambda 表达式
auto Function_comparison=[](ListNode* list1, ListNode* list2) {return list1->val > list2->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(Function_comparison)> pq_group;
// 关键字decltype可以让编译器找出表达式的类型
// 或者
// priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq_group(Function_comparison);
for(auto listnode:lists)
if (listnode!=nullptr)//要不为空才push
pq_group.push(listnode);//当前只是把节点头放进去而已
ListNode* result=new ListNode(0);//定义虚拟节点头
ListNode* p_result=result;//指针指向虚拟节点头
while(!pq_group.empty())//当队列不为空
{
ListNode* smallest_node=pq_group.top();//拿到第一个节点
pq_group.pop();//头个元素弹出
p_result->next=smallest_node;//赋值
if(smallest_node->next!=nullptr)//若不为空
{
pq_group.push(smallest_node->next);
}
p_result=p_result->next;
}
return result->next;
}
};
4. 单链表的倒数第 k 个节点
对于这类型的题目，最直接的方式当然就是先遍历一次得到链表的长度为n，然后再遍历一次得到倒数第k个节点（也就是正数的第n-k+1个节点）。 但这样做的话需要两次遍历，能否只遍历一次呢？
思路请见下图：
解题的代码如下，时间复杂度为O（N），空间复杂度为O（N）如果不额外用一个虚拟节点的话，空间复杂度为O（1）。
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* result=new ListNode(-1);//虚拟节点头，最后返回的为result->next
ListNode* p_result=result;//指向结果的指针
// 双指针法解题，遍历一次即可找到倒数第n个节点
ListNode* p1=head;//第一个指针，先指向head
for(int i=0;i<n;i++)//走n次
{
p1=p1->next;//指向它的下一个节点
}
ListNode* p2=head;//第二个指针，先指向head，并且跟p1一起走
while(p1!=nullptr)//一直往前走，直到到终点
{
p_result->next=p2;
p1=p1->next;//指向它的下一个节点
p2=p2->next;//p2跟随p1一起走
p_result=p_result->next;//跟随一起走
}
//此时，p2指向的就是倒数第n个，也就是顺数第size()-n+1个,
p_result->next=p2->next;//直接跳过当前p2指向的目标点
return result->next;
}
};
双指针法提取链表倒数第k个值。此题跟上一题其实是一样的，关键其实是输入数据构建成链表
#include <cstddef>
#include <iostream>
using namespace std;
struct ListNode{
int val;
ListNode* next;
//定义构造函数
ListNode(): val(0), next(nullptr) {}
ListNode(int value): val(value), next(nullptr) {}
ListNode(int value, ListNode* next): val(value), next(next) {}
};
int main() {
int num;
while(cin>>num)
{
// cin>>num;
ListNode* head=new ListNode(0);//虚拟的节点头，因此result为head->next
ListNode* p_head=head;
while(num--)
{
int temp;
cin>>temp;
ListNode* newnode=new ListNode(temp);
p_head->next=newnode;
p_head=p_head->next;//一直递推
}//注意此时num已经减完了
ListNode* p_1=head->next;//去掉了虚拟头节点
int k;
cin>>k;//输入获取倒数第k个值
while(k--)
{
p_1=p_1->next;//先让其走k步
}
ListNode* p_2=head->next;//初始化第二个指针
while(p_1!=nullptr)
{
// 再两个一起走，走到p1终点
p_1=p_1->next;
p_2=p_2->next;
}
std::cout<<p_2->val<<std::endl;//输出此时p2指向的值
}
}
4. 快慢指针获取单链表的中点
同样是双指针法，慢指针走一步，快指针走两步，这样当快指针走到终点时，慢指针就是中间点。
代码如下：
/**
* 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* middleNode(ListNode* head) {
//同样是双指针法，慢指针走一步，快指针走两步，这样当快指针走到终点时，慢指针就是中间点
// ListNode* result=new ListNode(-1);//虚拟头节点
ListNode* p_fast=head;//快指针走两步
ListNode* p_slow=head;//慢指针走一步
while(p_fast!=nullptr)
{
// 快指针走两步
p_fast=p_fast->next;
if(p_fast==nullptr)
break;
p_fast=p_fast->next;
// 注意：先走快指针，再走慢指针
// 当为奇数时，慢指针没有走，当为偶数时，慢指针走了
// 进而可以实现:如果有两个中间结点，则返回第二个中间结点。
p_slow=p_slow->next;//慢指针走一步
}
//当快指针指向终点时，慢指针指向的应该是中间值
// result->next=p_slow;
// return result->next;
return p_slow;//这样可以减少空间复杂度为O(1)，不用额外保留一个result,而时间复杂度均为O（N）
}
};
5. 快慢指针获取判断链表是否包含环
如果 fast 最终能正常走到链表末尾，说明链表中没有环；如果 fast 走着走着竟然和 slow 相遇了，那肯定是 fast 在链表中转圈了，说明链表中含有环。
时间复杂度为O（N）与空间为O（1）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
// 如果 fast 最终能正常走到链表末尾，说明链表中没有环；
// 如果 fast 走着走着竟然和 slow 相遇了，那肯定是 fast 在链表中转圈了，说明链表中含有环。
ListNode* p_fast=head;//快指针走两步
ListNode* p_slow=head;//慢指针走一步
while(p_fast!=NULL && p_fast->next!=NULL)
{
p_fast=p_fast->next->next;
p_slow=p_slow->next;
if(p_fast==p_slow)
return true;
}
return false;//能走出来
}
};
也可以采用hash table的形式来查看当前的节点是否已经访问过，如果访问过则说明有环，时间复杂度为O（N），空间复杂度为O（N）
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_map<ListNode *, int> ListNode_map;
while(head!=NULL)
{
ListNode_map[head]++;
if(ListNode_map[head]>1)//找到了一样的节点
return true;
head=head->next;
}
return false;
}
};
进阶版：如果链表中含有环，如何计算这个环的起点？
此题用哈希表解更加简单，空间复杂度与时间复杂度都是O(N)
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_map<ListNode *, int> group;
while(head!=NULL)
{
group[head]++;
if(group[head]>1)//找到了回环,而此必然为环的起点
return head;
head=head->next;
}
return NULL;
}
};
若要采用快慢指针，思路相对比较绕，请见图例。
注意跟哈希表不一样，快慢指针只是找到环的相遇点，而不是环的起点。快慢指针是通过判断是否有相遇点确定是否为环。而哈希表则是直接找到环的起点。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* p_fast=head;//快指针走两步
ListNode* p_slow=head;//慢指针走一步
// 先判断链表是否包含环
while(p_fast!=NULL && p_fast->next!=NULL)
{
p_fast=p_fast->next->next;
p_slow=p_slow->next;
if(p_fast==p_slow)
break;//不能直接返回p_slow,因为只是单纯的找到相遇点，而并非环的起点
}
// 如果遍历到了终点,那就是没有回环
if (p_fast==NULL || p_fast->next==NULL)
return NULL;
//否则,此时的p_fast与p_slow都是指向相遇点的.
// 当他们相遇时，p_fast走了2k，而p_slow走了k。p_fast多走的k步其实就是在环中转圈圈。
// 所以环长度必然为k
// 设相遇点距环起点为m。那么p_slow与p_fast再走k-m必然到环起点
// 而head走k-m也必然到环起点（此处请见图解析）
p_slow=head;//将p_slow重新指回起点,而此时p_fast是指向相遇点的
while(p_fast!=p_slow)//直到找到相遇点
{
// 快慢指针同步前进，相交点就是环起点
p_slow=p_slow->next;
p_fast=p_fast->next;
}
return p_slow;
}
};
6. 两个链表是否相交
最直接的解题思路应该是使用哈希集合存储链表节点，然后遍历另一个链表，看是否有相同的节点。时间复杂度为O（m+n），空间复杂度为O（m）或O（n）。
此处只看双指针法。解题思路见下图。时间复杂度为时间复杂度：O(m+n)，空间复杂度为O（1）
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1=headA;//先遍历A然后遍历B
ListNode *p2=headB;//先遍历B然后遍历A
while(p1!=p2)//直到找到相同的节点
{
if(p1==NULL)//到末端了
p1=headB;//将末端接上B
else
p1=p1->next;
if(p2==NULL)//到末端了
p2=headA;//将末端接上A
else
p2=p2->next;
}//当没有共同节点的时候，都为NULL，一起返回，反之返回的为他们的共同节点
return p1;
}
};
7. 删除排序链表中的重复元素
由于是已经排序的链表，最直接的思路应该是两两对比，如果遇到相同的就跳过去
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* p=head;//定义指向节点的指针
while(p!=nullptr && p->next!=nullptr)//循环一直到最后一个(同时避免第一个是空的)
{
if(p->val==p->next->val)//若当前的跟下一个是一样的
{
p->next=p->next->next;//相当于删掉了下一个
continue;//（可以不要！）到下一次循环，判断删掉当前后的下一个作为当前与它的下一个
}
else//不相同，那么就返回
p=p->next;//指针指向下一个节点，继续迭代
}
return head;//时间复杂度为O（N）
}
};
也可以采用快慢针法，具体见下动图解析以及代码：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
//定义快慢指针
ListNode* slow=head;
ListNode* fast=head;
while(fast!=nullptr)//一直遍历
{
if(slow->val!=fast->val)//如果不等，慢指针的下一个就指向快指针
{
slow->next=fast;
slow=slow->next;//慢指针继续走了
}
//如果相等，慢指针就不走了
fast=fast->next;
}
// 最后一个需要断开（自动释放掉不要的内存/不要的节点）
if (slow!=nullptr)
slow->next=nullptr;//由于前面并不是断掉节点的，最后一个slow可能是指向fast的下一个，所以需要断开
return head;//时间复杂度为O（N）
}
};
8. 其他链表类题目
除了上述的采用双指针法解决的链表类题目外，大部分的链表类题目其实都可以用递归来解决的。接下来逐一介绍
关于递归类题目的介绍，请见博客Link
两数相加
class Solution {
public:
// 采用递归的解法。并且通过审题可知，高位在尾节点
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry=0) {//carry 为进位
ListNode* result=new ListNode(0);//链表指针初始化为0
if(l1==nullptr && l2==nullptr) //如果两者都为空，那么就结束
return carry? new ListNode(carry):nullptr; //carry为空就没有，不为空就返回carry值生成的节点
//保证l1是最长的
if(l1==nullptr && l2!=nullptr)
swap(l1,l2);
carry=carry+l1->val+(l2 ? l2->val : 0);
result->val=carry%10;// 每个节点保存一个数位
carry=carry/10;//除10代表进位(存在l2为空)
//用递归迭代（注意题目正好是反过来的）
result->next=addTwoNumbers(l1->next,l2? l2->next:nullptr,carry);//由于保证了l1是最长的，只需要避免l2从空指针中访问next
return result;
//时间与空间复杂度均为O(N+M)
}
};
反转链表：全部
解决方法等效于在链表的头部插入一个节点，时间复杂度为O（N）：
class Solution {
public:
void calculate(ListNode* head, ListNode* &result)
{
if(head==nullptr)//到达末端
{
return;//返回
}
//若不为空，创建节点并且赋值
ListNode* newNode = new ListNode(head->val);
newNode->next = result; // 反转链表，将新节点的next指向前一个节点
// 注意不能result->next=result，这会导致无限循环，故此需要一个中间遍历来赋值
result = newNode; // 更新结果链表头节点
// 递归处理下一个节点
calculate(head->next, result);
}
ListNode* reverseList(ListNode* head) {
// ListNode* result=new ListNode();//这样做的话初始化为0而不是空
ListNode* result=nullptr;//初始化为空指针
// 采用递归的方式
calculate(head, result);
return result;
}
};
解法2:虽然写了很多指针，但是思路很清晰
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr || head->next==nullptr)
return head;//如果就是一个空指针或就只有一个值那么直接返回～
ListNode *pre= nullptr, *cur=head, *nxt=head->next;
while(cur!=nullptr)
{
//逐个节点反转
cur->next=pre;
//更新指针的位置
pre=cur;
cur=nxt;
if(nxt!=nullptr)
{
nxt=nxt->next;
}
}
return pre;// // 返回反转后的头结点
}
};
下面更好理解～
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr || head->next==nullptr)
return head;
ListNode *pre=nullptr,*cur=head;
while(cur!=nullptr)
{
ListNode *nxt=cur->next;
//上一个放到当前的下一个去，进行节点的反转
cur->next=pre;
// 更新节点的位置
pre=cur;//当前变为下一次的上一个
cur=nxt;//下一个放到当前
}
return pre;
}
};
反转链表：范围内
关键点在于右指针如何让递归回到改回到的点：
class Solution {
public:
void calculate(ListNode* head, const int left, const int right,ListNode* &result, int index)
{
if(head==nullptr)//到达了终点（head为空）
return;//为空则返回
if(index<left)//此时还不需要反转，顺序即可
{
ListNode* newlistnode=new ListNode(head->val);//用当前值创建链表。
result=newlistnode;//result为当前的值
calculate(head->next,left,right,result->next,index+1);//计算各自的下一个指针
}
else if(index>=left && index<=right)//需要倒序
{
ListNode* newlistnode=new ListNode(head->val);//当前的值
newlistnode->next=result;//当前的result作为next
result=newlistnode;//获取当前的值（此处类似在节点头插入一个节点）
calculate(head->next,left,right,result,index+1);
}
else if(index>right)//要恢复回顺序
{
// *关键：此时result的指针还是位于left上;要让它回到right上
// if(index<=right+(right-left+1))
// calculate(head,left,right,result->next,index+1);//指针递增
// else//回到right上了
// {
// result=head;//最后全部赋值
// return;
// }
// 让result的指针前进到right
int temp_int=right-left;
ListNode* p_result=result;
while(temp_int)
{
p_result=p_result->next;
temp_int--;
}
p_result->next=head;//将最后的全部直接赋值
return;
}
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* result=nullptr;//创建空的链表
int index=1;//从1开始
//用迭代的解法
calculate(head,left,right,result,index);
return result;
}
};
-->
K个一组反转链表
class Solution {
public:
//反转a到b的节点(其实就是head到null的变化版本)
ListNode* reverseab(ListNode* a, ListNode* b)
{
if(a==nullptr || a->next==nullptr)
return a;
ListNode *pre=nullptr, *cur=a;
while(cur!=b)
{
ListNode *nxt=cur->next;//获取当前的下一个
//逐个节点反转
cur->next=pre;//将上一个放到当前的下一个去
//更新节点的位置
pre=cur;//当前这个已经变为上一个了（下次用）
cur=nxt;//当前的下一个变为当前个
}
return pre;//返回反转后的节点头
}
ListNode* reverseKGroup(ListNode* head, int k) {
//满足k个反转，不满足k的部分不反转
ListNode *a=head;
ListNode *b=head;
//让b走k步
for(int i=0;i<k;i++)
{
if(b==nullptr)//先检查，不足k个不需要反转
return head;//不需要反转，直接返回
b=b->next;
}
// 反转a～b之间的 k 个元素
ListNode *newHead = reverseab(a, b);//注意里面进行了反转，故此a->next应该指向递归的新结果
// 递归反转后续链表并连接起来
a->next=reverseKGroup(b, k);//可以理解为上面把a～b改为了b～a为此应该是a->next接下一个
return newHead;
}
};
两两交换链表中的节点
此题有两个解决的思路:
第一是递归，也是最简单的：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 解法：递归
if(head==nullptr || head->next==nullptr)
return head;
ListNode* currentnode=new ListNode(head->val);//获取当前节点
currentnode->next = swapPairs(head->next->next);//而当前节点由于将会放在下一个，因此它的下一个为递归获得的下下个
ListNode* nextnode=head->next;//获取下一个节点
nextnode->next=currentnode;//当前节点为下一个节点的下一个节点
return nextnode;
}
};
下面是等效的写法，也是递归的思路：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 解法：递归
if(head==nullptr || head->next==nullptr)
return head;
ListNode* currentnode=head->next;//将下一个节点作为当前节点
head->next=swapPairs(head->next->next);//然后把原本的当前节点的下个节点指定为递归的结果，就是下下个节点
// head->next=swapPairs(currentnode->next);//这个也可以，但不利于理解
currentnode->next=head;//而原本的节点则为当前节点的下一个节点的
return currentnode;
}
};
第二个思路则是用指针遍历，逐一赋值，细心处理也可以避免出错，也很直接
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 解法2：链表迭代遍历以及，查询以及替换
ListNode* p=head;//指向节点的指针
while(p!=nullptr && p->next!=nullptr)//一直遍历到最后一个节点
{
ListNode* currentnode=new ListNode(p->val);//获取当前的节点
currentnode->next=p->next->next;//链接上下两个节点
ListNode* nextnode=new ListNode(p->next->val);//获取下一个节点
p->val=nextnode->val;//当前点赋值下一个点的值
p->next=currentnode;//而当前点的下一个则链接上原本的当前点
p=p->next->next;//跳两个，如果跳过两个后为空就跳出
}
return head;
}
};
移除链表元素
解题思路很简单，其实就是基本的去除链表某个元素而已~
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* p=head;//作为迭代的指针
// 改为永远判断下一个
while(p!=nullptr && p->next!=nullptr)
{
auto nextnode=p->next;
if(nextnode->val==val)//若下一个节点为目标值
{
p->next=p->next->next;
}
else
{
p=p->next;//一直迭代
}
}
// 最后检查第一个（不要漏了~）
if(head!=nullptr && head->val==val)
{
ListNode* newnode=head->next;
head=newnode;
}
return head;
}
};
从单向链表中删除指定值的节点
题目其实跟上面的移除链表元素一样，难点其实在于输入数据的管理以及构建链表的过程（注意链表的生成过程是需要先找前面的数，然后插入，原本的下一个链表为当前链表的next）～
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
// 构造函数
ListNode() :val(0), next(nullptr) {}
ListNode(int value) :val(value), next(nullptr) {}
ListNode(int value, ListNode *next) :val(value), next(next) {}
};
int main() {
int totally_num, first_val;
cin>>totally_num>>first_val;
//创建虚拟头链表
ListNode *head=new ListNode();
head->val=first_val;
totally_num--;//第一个应该去掉（关键！）
int aft,pre;
while(totally_num--)
{
cin>>aft>>pre;
ListNode *newnode=new ListNode(aft);
ListNode *p_head=head;
while(p_head!=nullptr)
{
if(p_head->val==pre)//找到了
{
break;
}
else
p_head=p_head->next;//一直递推
}
if(p_head!=nullptr)//上面找到对应值啦
{
auto temp=p_head->next;//原本的下一个值
p_head->next=newnode;
newnode->next=temp;
}
}
int target_value;
cin>>target_value;
ListNode *p_head=head;
while(p_head!=nullptr && p_head->next!=nullptr)//永远判断下一个
{
auto nextnode=p_head->next;
if(nextnode->val==target_value)//找到了
{
p_head->next=p_head->next->next;//将当前的下一个指向下下个
}
else
{
p_head=p_head->next;//一直递推
}
}
//最后检查头节点
if(head!=nullptr && head->val==target_value)
{
ListNode* newnode=head->next;
head=newnode;
}
//最后逐输出
while(head!=nullptr)
{
std::cout<<head->val<<" ";
head=head->next;//一直递推
}
}
参考资料
- 解说视频
- 双指针技巧秒杀七道链表题目
- My Leetcode
- 什么是双向链表(跟单向链表很像)？
- 关于cpp中优先级队列如何使用，请见：cpp中优先级队列的使用
