目录

反转链表

题目

​编辑

分析

代码

k个一组翻转链表

题目

分析

代码

两两交换链表中的结点

题目

​编辑

分析

代码

---

反转链表

题目

分析

反转过程:

• newhead作为遍历指针,最终停在尾结点上
• prev保存上一个结点,通过改变newhead和prev的连接来实现反转(核心)
• 通过next保存原链表的下一个结点,防止反转连接关系后找不到原结点
• 

经过一轮循环后,第一个和第二个结点的连接成功反转,之后就不断循环该过程,直到next指向空

• 

代码

/*** 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* reverseList(ListNode* head) {ListNode *pre = nullptr, *next = head;while (next) {next = head->next;head->next = pre;pre = head;head = next;}return pre;}
};

实在记不住原理,可以记代码:

• 首先定义前后继指针
• 循环条件:后继结点指向空
• 循环体:后继指针指向下一个结点,prev指引head->next的指向关系,prev跟着head走,head跟着next走

注意等号两边是对称的嗷: 

• 

k个一组翻转链表

题目

分析

还是基于反转链表的思路,难点在于先筛选出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) {ListNode* tmp = head;//查看当前是否还有k个剩余结点for (int i = 0; i < k; ++i) {if (tmp == nullptr) {return head;}tmp = tmp->next;}//对当前这四个结点进行反转ListNode *pre = nullptr, *next = head, *cur = head;while (cur != tmp) {next = cur->next;cur->next = pre;pre = cur;cur = next;}//反转后,head成为新的尾结点,来链入后续部分head->next = reverseKGroup(tmp, k);//返回给前面部分新的头结点return pre;}
};

两两交换链表中的结点

题目

分析

类似于上道题的思路,只是更简单了一点 -- 因为不需要进行组内反转了

• 相当于直接给出了新的头尾结点
• 依然可以将两个结点看为一组,只需要重新对二者进行链接,然后将头结点返回,尾结点接收返回值就行

代码

/*** 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) {return nullptr;}if (head->next == nullptr) {return head;}ListNode *new_head = head->next, *next = new_head->next;head->next = swapPairs(next);new_head->next = head;return new_head;}
};