画图分析:Happy coding! Enjoy Algorithms.第{14}天 lc{ 15} K 个一组翻转链表
输入:head = [1,2,3,4,5], k = 2 输出:[2,1,4,3,5]
提示:能用文字表达出来嘛?
翻转链表:需要三个变量 (固定头节点,链表第一个节点,也是翻转后最后一个节点,当前阶段)
提示:在不运行代码情况下。通过简单例子验证 是否正确。逻辑推理能力。
在不运行代码情况下。通过简单例子验证 是否正确。逻辑推理能力。这个没做到
//移动left-1次.【left,right】
for(int i=0;i<left-1;i++)
{
phead =pcur;//?????????phead =ppre
ppre = pcur;
pcur =pcur->next;
cout << "phead =" <<phead->val << " ppre =" <<ppre->val
<< " pcur =" <<pcur->val <<endl;
}
pcur =pcur->next; vs pcur =ppre->next;
/*
* @lc app=leetcode.cn id=25 lang=cpp
*
* [25] K 个一组翻转链表
*/
// @lc code=start
/**
* 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* reverseGroup(ListNode* head,int k);
ListNode* reverseKGroup(ListNode* head, int k) {
//01
if (nullptr == head || nullptr ==head->next || 1 ==k)
{
return head;
}
//02
ListNode myhead;
myhead.next =head;
int count =0;
while(head)
{
count++;
head =head->next;
}
head =myhead.next;
//03 循环次数:count/k
ListNode* phead =&myhead;
ListNode* ppre =head;
ListNode* pcur =head->next;
//phead->1(ppre)-->2(pcur) --3--4 -5
//默认第一个元素不用翻转,
//第一个元素翻转后变成最后一个元素
// head>--2---1(pre) ->3(pcur) --4()
//head>2-1(phead) -->3(ppre) -->4(pcur)
//len -= k;
int j =count/k;
while( j-->0)
{
for(int i=0;i<k-1;i++)
{
ppre->next =pcur->next;
pcur->next =phead->next;
phead->next = pcur;
pcur =ppre->next;
}
if(pcur)
{
phead =ppre;
ppre =pcur;
pcur =pcur->next;
}
}
return myhead.next;
}
};
// @lc code=end
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/zui-nan-lian-biao-ti-liao-jie-yi-xia-javapythonjav/