复习Day11：链表part04: 206. 反转链表、92. 反转链表II、25. K 个一组翻转链表、148. 排序链表

我用的方法是在leetcode再过一遍例题，明显会的就复制粘贴，之前没写出来就重写，然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了，使用leetcode自带的IDE模拟面试环境。

哈希表章节的题目思路很清晰，主要是C++中的写法。

206. 反转链表

如何使用递归解法反转整个 单链表：

class Solution {
public:ListNode* reverseList(ListNode* head) {/* 递归解法 */return reverse(head);}ListNode* reverse(ListNode *head){if(head == nullptr || head->next == nullptr){return head;}ListNode* last = reverse(head->next);head->next->next = head;head->next = nullptr;return last;}
};

reverse 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

原来的链表：

[外链图片转存中…(img-KLgVmb78-1696603051839)]

运行完

ListNode last = reverse(head.next);

[外链图片转存中…(img-J17okqo4-1696603051839)]

链表变成了这样（先不要管递归的压栈的实现细节）：

[外链图片转存中…(img-d2chnyBs-1696603051840)]

然后运行

head.next.next = head;

[外链图片转存中…(img-nOEn10VM-1696603051840)]

接下来把head->next指向null，并返回现在的头节点：last

head->next = nullptr;
return last;

[外链图片转存中…(img-dQVs9BKX-1696603051840)]

1、递归函数要有 base case，也就是这句：

if (head == NULL || head->next == NULL) {return head;
}

意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

2、当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：

head->next = NULL;

92. 反转链表II

leetcode链接：https://leetcode.cn/problems/reverse-linked-list-ii/

给你单链表的头指针 head 和两个整数 left 和 right ，
其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

如何反转单链表的一部分？这里迭代解法在之前完全反转链表中已经说过了，这里重点关注递归法 。

(迭代的思路大概是：先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转)

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

[外链图片转存中…(img-0ZYveRdG-1696603051840)]

此题见：https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-8f30d/ru-he-k-ge-d591d/

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {if (head == nullptr) return nullptr;// 区间 [a, b) 包含 k 个待反转元素ListNode *a, *b;a = b = head;for (int i = 0; i < k; i++) {// 不足 k 个，不需要反转，base caseif (b == nullptr) return head;b = b->next;}// 反转前 k 个元素ListNode *newHead = reverse(a, b);// 递归反转后续链表并连接起来a->next = reverseKGroup(b, k);return newHead;}ListNode* reverse(ListNode* a, ListNode* b) {ListNode *pre, *cur, *nxt;pre = nullptr; cur = a; nxt = a;// while 终止的条件改一下就行了while (cur != b) {nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}// 返回反转后的头结点return pre;
}
};

148. 排序链表

class Solution {
public:ListNode* sortList(ListNode* head) {return sortList(head, nullptr);}ListNode* sortList(ListNode* head, ListNode* tail) {if (head == nullptr) {return head;}if (head->next == tail) {head->next = nullptr;return head;}ListNode* slow = head, *fast = head;while (fast != tail) {slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next;}}ListNode* mid = slow;return merge(sortList(head, mid), sortList(mid, tail));}ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummyHead = new ListNode(0);ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;while (temp1 != nullptr && temp2 != nullptr) {if (temp1->val <= temp2->val) {temp->next = temp1;temp1 = temp1->next;} else {temp->next = temp2;temp2 = temp2->next;}temp = temp->next;}if (temp1 != nullptr) {temp->next = temp1;} else if (temp2 != nullptr) {temp->next = temp2;}return dummyHead->next;}
};