国外服务器推荐_小商品批发网_服装品牌营销策划方案_百度软件商店

从表头开始遍历，找到组内最后一个节点，同时检查剩余节点是否大于等于K

根据组内表头节点和表尾结点对子链表进行翻转，同时返回新的头和尾

继续遍历链表寻找需要进行翻转的子链表进行翻转

根据返回的新的头和尾将子链表和原有链表进行连接，直至不在有k个节点

其中，子链表翻转和返回新头尾的图示如下：:

0：初始状态

        ListNode* prev = tail->next;
        ListNode* p = head;

1： 进行翻转

        p->next = prev;

2：翻转后更新节点

        prev = p;

        p = nex;

3： 继续进行翻转

        p->next = prev;

4：翻转后更新节点

        prev = p;

        p = nex;

 

此时prev == tail子链表翻转结束 ，返回新的头（tail）尾（head）

翻转后子链表和原有链表进行连接的图示如下：

ListNode* nex = tail->next;

pre->next = head;

tail->next = nex;

 链接后指针的更新（方便进行下一次翻转）

 

/*** 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:pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail){ListNode* prev = tail->next;ListNode* p = head;while(prev != tail){ListNode* nex = p->next;p->next = prev;prev = p;p = nex;}return {tail, head};}ListNode* reverseKGroup(ListNode* head, int k) {ListNode* hair = new ListNode(0, head);ListNode* pre = hair;while(head){ListNode* tail = pre;for(int i = 0; i < k; i++){tail = tail->next;if(!tail){return hair->next;}}ListNode* nexNode = tail->next;//翻转当前分组内节点，获取新翻转区间的头尾指针tie(head, tail) = myReverse(head, tail);//将翻转后的子链表与原链表连接起来pre->next = head;tail->next = nexNode;pre = tail;head = tail->next;}return hair->next;}
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)