leetcode-025

题目

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，则这一部分不需要反转。

解法

对于此题，我的想法是写两个函数来解决问题：

分解链表的函数，把链表分解成长度为k的各个子链表
反转一段链表的函数，用于反转分解后得到的子链表

先实现反转一段链表的函数，这个函数比较容易实现，我们也经常遇到这种问题。实现的思路是用curr指针遍历链表，用pre记录curr的前一项，在遍历的过程中，把curr->next指向pre，再把pre赋值给curr，一直遍历下去，这样就完成了链表的反转，时间复杂度为O(n)，空间复杂度为O(1)。

稍微难一点的是分解链表的函数，因为链表长度未知，在分解完成、反转完成后还要连接各个子链表，因此不仅需要各个子链表的头，还要各个子链表的尾，而为了满足O(1)的空间复杂度，最好是在遍历的过程中分别用两个变量来记录头和尾，而不能另外开辟空间。

我的思路是：遍历一遍链表，通过count来计数，count ！= k时count++，继续遍历；当count == k时即找到一个子链表，反转这个子链表，并与前面已经完成反转操作的子链表连接，count设为0，再继续遍历。

在这之中需要注意几点：

要记录最终链表的头用以返回，这即是第一个反转后的子链表的头
每次分解需要记录子链表的头和尾，即更新curr_head和curr_tail
要注意处理链表长度不是k的倍数和k大于链表长度的情况

弄明白了这几点之后代码也就不难实现了，但这种解法的效率貌似并不高，应该是由于分解链表的效率低，因此还需要找更好的算法。

代码

class Solution {
public:
    //反转一段链表
    ListNode* reverse_List(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *curr = head, *prev = NULL;
        while (curr->next != NULL) {
            ListNode* tmp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tmp;
        }
        curr->next = prev;
        return curr;
    }
    //先把整段链表分解成每k个一段，再对每一段进行反转，最后连接起来
    ListNode* reverseKGroup(ListNode* head, int k) {
        int count = 0;//用于计算一段链表的长度
        ListNode* tmp = head;
        ListNode* curr_head = head;//用作小段链表的头
        ListNode* curr_tail = NULL;//当前已完成反转部分链表的尾

        ListNode* result_head = NULL;

        while (tmp != NULL) {
            count++;
            if (count == k) {
                ListNode* remaining = tmp->next;
                tmp->next = NULL;
                curr_head = reverse_List(curr_head);//反转小段链表
                if (result_head == NULL) result_head = curr_head;
                if (curr_tail != NULL) curr_tail->next = curr_head;
                while (curr_head->next != NULL) {
                    curr_head = curr_head->next;
                }
                curr_tail = curr_head;
                curr_head = remaining;
                tmp = remaining;
                count = 0;
            }
            else tmp = tmp->next;
        }
        //输入的链表长度不是k的倍数时会剩下未反转的部分链表
        if (count != 0 && curr_tail != NULL) curr_tail->next = curr_head;
        //输入的k大于链表长度的情况
        else if (count != 0 && curr_tail == NULL) return head;
        return result_head;
    }
};