25.Reverse Nodes in k-Group

Tags: Hard Linked List

Links: https://leetcode.com/problems/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.

---

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //空链表，或者只有一个节点，或者k为1，直接返回
        if (!head || !head -> next || k == 1) return head; 

        ListNode *dummy = new ListNode(0);
        dummy -> next = head;
        ListNode * pre = head, * cur = pre -> next, *top = dummy;
        int cnt = 0; //计数器，记录走过多少个节点
        ListNode *prob = top; //探测指针，判断何时到达尾部

        //开始翻转
        while (true) {
            cnt = 0;
            while (prob -> next && cnt < k) {
                prob = prob -> next;
                ++cnt;
            }
            if (cnt != k) break;
            for (int i = 1; i <= k - 1; ++i){
                pre -> next = cur -> next;
                cur -> next = top -> next;
                top -> next = cur;
                cur = pre -> next;
            }
            top = pre;
            prob = top;
            pre = pre -> next;
            if (!pre) break;
            else cur = pre -> next;
        }

        return dummy -> next;
    }
};

虽然是hard的题目，但是思路很明显，注意细节就可以。

翻转链表的局部，肯定需要三个辅助指针，其中两个用于翻转，一个用来做虚拟头部。另外由于是部分翻转，可能存在长度小于要求长度的情况，所以需要一个探测指针和一个计数器，探测指针探测什么时候到尾端，计数器用来记录走过的节点，和题目19.Remove Nth Node From End of List思路很是接近。