leetcode Hot 100系列
文章目录
- 一、翻转链表
- 二、反转链表 II
- 三、K 个一组翻转链表
- 总结
一、翻转链表
- 建立pre为空，建立cur为head，开始循环：先保存cur的next的值，再将cur的next置为pre，将pre前进到cur的位置，再将cur往前进一步(利用刚刚保存的值)，直到cur为nullptr
代码如下：
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur=head;ListNode* pre=nullptr;while (cur!=nullptr){ListNode* temp=cur->next;cur->next=pre;pre=cur;cur=temp;}return pre; }
};
提示：小白个人理解，如有错误敬请谅解！
二、反转链表 II
- 这个和上面的区别就是从left开始，为了防止left为head，这样就没有p0了，所以要加入dummyhead，并且将dummyhead和head连起来
- 先要找到left位置的前一个作为p0，然后继续上面的操作，初始化pre为空，cur为p0的next，然后开始循环（循环的次数就是要翻转的个数）：先保存cur的next位置，再将cur的next指向pre，随后pre到cur的位置，最后cur到之前保存的cur的next位置上，循环结束了之后，将p0的next的next指向cur，再才能将p0的next指向pre(如果这两个顺序反了，那由于先改变了p0的next的位置，再修改p0的next的next的时候，指向的位置就已经变了)
代码如下：
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummyhead=new ListNode(0);dummyhead->next=head;ListNode* p0=dummyhead;int m=left;m--;while (m--){ p0=p0->next;}ListNode* pre=nullptr;ListNode* cur=p0->next;int n=right-left+1;while (n--){ListNode* temp=cur->next;cur->next=pre;pre=cur;cur=temp;}p0->next->next=cur;p0->next=pre;return dummyhead->next;}
};
三、K 个一组翻转链表
- 设置dummyhead，并且令p0为dummyhead，这样p0才是要翻转的链表的前一个
- 由于k组翻转链表，所以要先统计一下一共有多少个，每次循环(翻转了k个链表)就将这个总数减k，然后看剩下的值到不到k，如果到了才能继续进行循环
- 设置pre为空，cur为p0的next，开始小循环，最后结束之后，先要保存一下p0的next作为下一个要翻转的链表的p0，然后再继续之前的操作，将p0的next的next置为cur，再将p0的next置为pre，最后将p0设置为之前保存的p0的next值，由下图中可知对于下一组k的链表来说，他们的p0应该是 1 这个节点，也就是最开始保存的保存的p0的next
图源@灵茶山艾府 - 返回dummyhead的next
代码如下：
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummyhead=new ListNode(0);dummyhead->next=head;ListNode* curr=head;int count=0;while (curr!=nullptr){curr=curr->next;count++;}ListNode* p0=dummyhead;while (count>=k){ count-=k;ListNode* pre=nullptr;ListNode* cur=p0->next;int m=k;while (m--){ListNode* temp=cur->next;cur->next=pre;pre=cur;cur=temp;}ListNode* nxt=p0->next;p0->next->next=cur;p0->next=pre;p0=nxt;}return dummyhead->next;}
};
总结
- pre统一设置为空，cur设置为p0的next，使用临时变量接受cur的next，最后要更新p0的位置！