【刷题篇】反转链表

文章目录

一、206.反转链表
二、92.反转链表 ||
三、25. K 个一组翻转链表

一、206.反转链表

在这里插入图片描述

class Solution {
public://使用头插//三个指针也可以ListNode* reverseList(ListNode* head) {if(head==nullptr)return nullptr;ListNode* cur=head;ListNode* newhead=new ListNode(0);ListNode* pre=newhead;while(cur){ListNode* next=cur->next;cur->next=pre->next;pre->next=cur;cur=next;}cur=newhead->next;delete newhead;return cur;}
};

二、92.反转链表 ||

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

在这里插入图片描述

/更简洁
class Solution {
public:ListNode *reverseBetween(ListNode *head, int left, int right) {ListNode *dummy = new ListNode(0, head), *p0 = dummy;for (int i = 0; i < left - 1; ++i)p0 = p0->next;ListNode *pre = nullptr, *cur = p0->next;for (int i = 0; i < right - left + 1; ++i) {ListNode *nxt = cur->next;cur->next = pre; // 每次循环只修改一个 next，pre = cur;cur = nxt;}p0->next->next = cur;p0->next = pre;return dummy->next;}
};// class Solution {
// public://使用头插，使用哨兵节点，left可能为一
//     ListNode* reverseBetween(ListNode* head, int left, int right) {
//         if(left==right)
//         {
//             return head;
//         }
//         int sign=1;
//         ListNode* cur=head;
//         ListNode* newhead=new ListNode(0);
//         ListNode* tmp=newhead;
//         ListNode* firstinsert=nullptr;
//         while(cur)
//         {
//             ListNode* next=cur->next;
//             if(sign==left)
//             {
//                 firstinsert=cur;
//             }
//             if(sign>=left&& sign<=right)
//             {
//                 cur->next=tmp->next;
//                 tmp->next=cur;
//                 cur=next;
//                 if(sign==right)
//                 {
//                     tmp=firstinsert;
//                     if(cur==nullptr)
//                     {
//                         firstinsert->next=nullptr;
//                     }
//                 }
//             }
//             else
//             {
//                 tmp->next=cur;
//                 tmp=cur;
//                 cur=next;  
//             }
//             sign++;
//         }
//         cur=newhead->next;
//         delete newhead;
//         return cur;
//     }
// };

三、25. K 个一组翻转链表

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

class Solution {
public://思路是进行头插ListNode *reverseKGroup(ListNode *head, int k) {//先遍历链表，看需要反转几次int n=0;ListNode* cur=head;while(cur){cur=cur->next;n++;}n=n/k;//这就是要反转几次的结果cur=head;ListNode* newhead=new ListNode(0);ListNode* pre=newhead;for(int i=0;i<n;i++){ListNode* tmp=cur;for(int i=0;i<k;i++){ListNode* next=cur->next;cur->next=pre->next;pre->next=cur;cur=next;}pre=tmp;}//处理不需要反转的pre->next=cur;cur=newhead->next;delete newhead;return cur;}
};