Leetcode 25.Reverse Nodes in k-G

原题地址：https://leetcode.com/problems/reverse-nodes-in-k-group/description/

题目描述

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.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For 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

就是说以k个节点为单位，把链表里每k个节点的值的顺序反转。剩下的不足k个的节点不用处理。

解题思路

一个指针current用于遍历链表，一个指针last_pos用于保存上一次更新结束以后更新到的范围，一个vector用来存放节点值，一个整数count用来计数。
current遍历链表，每遍历满k个就从last_pos指向的节点开始，更新k个节点，值从vector里取。一次更新完之后清空vector，count置0，反复操作直到链表的尽头。

代码

/**
 * 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) {
        vector<int> vec;
        ListNode * last_pos =head;
        ListNode * current = head;
        int count = 0;
        while(current!=NULL ){
            vec.push_back(current->val);
            count++;
            current=current->next;
            if(count==k){
                for(int i =0;i<k;i++){
                    last_pos->val = vec[vec.size()-1-i];
                    last_pos=last_pos->next;
                }
                vec.clear();
                count=0;
            }
        }
        return head;
    }
};

坑点：

不存在的。

TIM截图20170917003235.png