所谓反转链表,就是对一个单向的链表进行反转,例如:
1->2->3->4->5->6
反转过后就是:
1<-2<-3<-4<-5<-6
那么这个该怎么做呢?
我们从题目中获取一些灵感吧
1.反转链表
题目链接:Leetcode 206.反转链表
通过题目可知,这个题其实并没有难度,只需要遍历一次链表,将其中的每一个节点都反转即可:
/**
* 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;
ListNode *cur = head;
while (cur != nullptr) {
ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
看完最基础的反转链表以后,我们再来看看更加高阶的反转链表问题
2.反转链表Ⅱ
题目链接:leetcode 92.反转链表Ⅱ
这个题与刚才的题目不同的是,本题是要实现链表的局部反转,我们从刚才的题目里已经学会了反转链表的方法,以此类推,我们看看能否将刚才的操作运用到这个题里面来
以上图为例,我们要反转这个局部的链表,实际上就是需要反转2->3->4
这个子链表,因此我们需要做的事情是:
- 将子链表提出来
- 反转子链表
- 将子链表插回原链表中
因此,我们需要保存以下几个节点的信息:子链表前的一个节点(1号节点)、子链表的第一个节点(2号节点)、子链表的最后一个节点(4号节点),以及子链表的后一个节点(5号节点)。
首先,我们将子链表从这个链表中抽离,即断开1号节点与2号节点的连接,断开4号节点和5号节点之间的连接,然后将子链表反转,再将1号节点与4号节点相连,将2号节点与5号节点相连
看明白了过程我们就开始写代码了(注意:在这里我使用了一个幻影节点,用于减少不必要的分类讨论,例如如果要反转的首节点是第一个,那么就不需要再进行单独写代码进行讨论了):
/**
* 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* findNthNode(ListNode* head, int n) {
// 遍历寻找该节点后的第n个节点
ListNode* node = head;
while (node->next != nullptr && n--) {
node = node->next;
}
return node;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
// 1. 寻找断开节点1和2
// 2. 断开节点 && 倒序排列节点
// 3. 重新连接
ListNode* shadowHead = new ListNode(0, head);
if (head == nullptr || left == right) {
return head;
}
// 寻找节点1和节点4
ListNode* begin = findNthNode(shadowHead, left-1);
ListNode* end = findNthNode(shadowHead, right);
// 节点2和节点5
ListNode* begin2 = begin->next;
ListNode* end2 = end->next;
// 断开节点
begin->next = nullptr;
end->next = nullptr;
// 反转子链表
ListNode* pre = nullptr;
ListNode* cur = begin2;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
// 将子链表插回原链表中
begin->next = end;
begin2->next = end2;
return shadowHead->next;
}
};
3.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* reverseListNode(ListNode* begin, ListNode* end) {
// 这个部分和反转链表2的代码一样的
ListNode* begin2 = begin->next;
ListNode* end2 = end->next;
begin->next = nullptr;
end->next = nullptr;
ListNode* pre = nullptr;
ListNode* cur = begin2;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
begin->next = end;
begin2->next = end2;
return begin;
}
ListNode* findNthNode(ListNode* head, int n) {
// 往后第n个节点
while (head->next != nullptr && n--) {
head = head->next;
}
return head;
}
int ListSize(ListNode* head) {
// 获取链表的长度
int ans = 1;
while (head->next != nullptr) {
head = head->next;
ans++;
}
return ans;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr || k == 1) {
return head;
}
ListNode* shadowHead = new ListNode(0, head);
int size = ListSize(head);
size = size - (size % k);
for (int i = 0; i < size; i += k) {
// 挨个反转链表
reverseListNode(findNthNode(shadowHead, i),
findNthNode(shadowHead, i + k));
}
return shadowHead->next;
}
};
作者:NorthCity1984
出处:https://grimoire.cn/acm/reverse-listnode.html
版权:本文《【leetcode题解】反转链表》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
出处:https://grimoire.cn/acm/reverse-listnode.html
版权:本文《【leetcode题解】反转链表》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
评论