|
?目录
反转单链表
反转部分单链表
K个一组反转单链表
K个一组反转单链表(从尾结点开始)
反转单链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点
输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
class?Solution?{
public:
????ListNode*?reverseList(ListNode*?head)?{
????????if(head?==?NULL?||?head->next?==?NULL)
????????????return?head;
????????ListNode?*cur?=?head;
????????ListNode?*pre?=?NULL;
????????ListNode?*tmp?=?NULL;
????????while(cur){
????????????tmp?=?cur->next;
????????????cur->next?=?pre;
????????????pre?=?cur;
????????????cur?=?tmp;
????????}
????????return?pre;
????}
};
反转部分单链表
反转left到right部分的链表节点
class?Solution?{
private:
????void?reverseLinkedList(ListNode?*head)?{
????????//?也可以使用递归反转一个链表
????????ListNode?*pre?=?nullptr;
????????ListNode?*cur?=?head;
????????while?(cur?!=?nullptr)?{
????????????ListNode?*next?=?cur->next;
????????????cur->next?=?pre;
????????????pre?=?cur;
????????????cur?=?next;
????????}
????}
public:
????ListNode?*reverseBetween(ListNode?*head,?int?left,?int?right)?{
????????//?因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
????????ListNode?*dummyNode?=?new?ListNode(-1);
????????dummyNode->next?=?head;
????????ListNode?*pre?=?dummyNode;
????????//?第?1?步：从虚拟头节点走?left?-?1?步，来到?left?节点的前一个节点
????????//?建议写在?for?循环里，语义清晰
????????for?(int?i?=?0;?i?<?left?-?1;?i++)?{
????????????pre?=?pre->next;
????????}
????????//?第?2?步：从?pre?再走?right?-?left?+?1?步，来到?right?节点
????????ListNode?*rightNode?=?pre;
????????for?(int?i?=?0;?i?<?right?-?left?+?1;?i++)?{
????????????rightNode?=?rightNode->next;
????????}
????????//?第?3?步：切断出一个子链表（截取链表）
????????ListNode?*leftNode?=?pre->next;
????????ListNode?*curr?=?rightNode->next;
????????//?注意：切断链接
????????pre->next?=?nullptr;
????????rightNode->next?=?nullptr;
????????//?第?4?步：同第?206?题，反转链表的子区间
????????reverseLinkedList(leftNode);
????????//?第?5?步：接回到原来的链表中
????????pre->next?=?rightNode;
????????leftNode->next?=?curr;
????????return?dummyNode->next;
????}
};
K个一组反转单链表
给出头结点，从前往后，不足k个的不反转
class?Solution?{
public:
????ListNode*?reverseKGroup(ListNode*?head,?int?k)?{
????????if?(head?==?nullptr)????return?head;
????????ListNode*?tail?=?head;
????????for(int?i?=?0;?i?<?k;?++i)??//先让tail移动k个节点
????????{
????????????if(tail?==?nullptr)?return?head;
????????????tail?=?tail->next;
????????}
????????ListNode*?cur?=?head,?*pre?=?nullptr,?*next?=?nullptr;
????????while(cur?!=?tail)??????//注意：?reverse[head,?tail)
????????{
????????????next?=?cur->next;
????????????cur->next?=?pre;
????????????pre?=?cur;
????????????cur?=?next;
????????}
????????head->next?=?reverseKGroup(tail,?k);??//@在本组中，head成为了最后一个节点，注意递归使用(tail,?k)
????????return?pre;?????//@返回翻转后的头结点
????}
};
K个一组反转单链表(从尾结点开始)
在上一个题的基础上，如果给定的是尾结点，从后开始反转。则：
你只需要先把单链表进行一次逆序，逆序之后就能转化为从头部开始组起了，然后按照我上面的解法，处理完之后，把结果再次逆序即搞定。两次逆序相当于没逆序。
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。
class?Solution?{
public:
????ListNode*?reverse1(ListNode*?head){
????????if(head?==?nullptr?||?head->next?==?nullptr)
????????????return?head;
????????ListNode*?cur?=?head;
????????ListNode*?pre?=?nullptr;
????????ListNode*?tmp?=?nullptr;
????????while(cur){
????????????tmp?=?cur->next;
????????????cur->next?=?pre;
????????????pre?=?cur;
????????????cur?=?tmp;
????????}
????????return?pre;
????}
????ListNode*?reverseKGroup1(ListNode*?head,?int?k)?{
????????if?(head?==?nullptr)????return?head;
????????ListNode*?tail?=?head;
????????for(int?i?=?0;?i?<?k;?++i)??//先让tail移动k个节点
????????{
????????????if(tail?==?nullptr)?return?head;
????????????tail?=?tail->next;
????????}
????????ListNode*?cur?=?head,?*pre?=?nullptr,?*next?=?nullptr;
????????while(cur?!=?tail)??????//注意：?reverse[head,?tail)
????????{
????????????next?=?cur->next;
????????????cur->next?=?pre;
????????????pre?=?cur;
????????????cur?=?next;
????????}
????????head->next?=?reverseKGroup1(tail,?k);??//@在本组中，head成为了最后一个节点，注意递归使用(tail,?k)
????????return?pre;?????//@返回翻转后的头结点
????}
????ListNode*?reverseKGroup(ListNode*?phead,?int?k){
????????ListNode*?head?=?reverse1(phead);
????????ListNode*?tmp?=?reverseKGroup1(head,?k);
????????ListNode*?res?=?reverse1(tmp);
????????return?res;
????}
};
|