25. Reverse Nodes in k-Group

问题描述

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

题解

题目要求每k个节点一组进行翻转，返回反转后的链表。可以将算法分为两部分：分组+链表翻转；还要注意的是，如果剩余节点数目不够k个，不进行翻转，直接链接到上一组的链表上。

步骤：

1. 记录链表长度；
2. 循环，条件是剩余链表长度不小于k
3. 一边计数一边翻转：
   1. 使用指针pre表示上一次翻转结果的链表尾，如果还没有进行翻转，设置为新声明的dummy节点；
   2. 指针cur表示需要翻转的节点；初始设置为pre指针的下一个节点；
   3. 进行翻转：
      1. 声明temp指针：记录cur的下一个节点
      2. 进行单节点的翻转；
      3. pre指针的下一个节点始终表示当前组翻转的头结点，所以每次反转后都要更新pre的next指针；
4. 更新pre指针为cur；（cur指针指向当前组的最后一个节点）
5. 更新链表长度k；

代码：

/**
 * 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* reverseKGroup(ListNode* head, int k) {
        ListNode *first = new ListNode(-1), *pre = first, *cur = first;
        first->next = head;
        
        int len = 0;
        // 记录链表长度
        while (cur = cur->next) ++len;
        // 训练分组反转链表
        while (len >= k){
            //记录需要翻转链表的起始节点
            cur = pre->next;
            //依次翻转，对组内的k个节点翻转
            for (int i=1; i< k; ++i){
                ListNode *temp = cur->next;
                cur->next = temp->next;
                temp->next = pre->next;
                
                pre->next = temp;
            }
            pre = cur;
            len -= k;
        }
        
        return first->next;
    }
};

没有想到这里的翻转方式；想到的是先找到k个节点的子链表；然后翻转，最后更新链接指针；这种方法应该也可以，过两天回顾时再看看。

Reference

https://www.cnblogs.com/grandyang/p/4441324.html

---

欢迎关注公众号，一起学习