[LeetCode]Reverse Nodes in k-Group

和普通的Reverse Linked List是类似的，难点就是我们要分块reverse了。有两种解法，递归和循环。递归的做法就是每次reverse k个node，然后继续递归reverse右边的节点，当前的尾巴连向右边新reverse之后的头节点。时间复杂度O(N), 空间复杂度因为有递归是O(N / k)：

	/**
	* 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) {
	if(k <= 1)return head;
	return reverse(head, k);
	}
	private:
	ListNode* reverse(ListNode* head, int k)
	{
	if(!head)return head;
	int i = k - 1;
	ListNode* end = head;
	while(i-- && end)end = end->next;
	if(!end)return head;
	ListNode* curr = head->next, *prev = head;
	while(prev != end)
	{
	ListNode* tmp = curr->next;
	curr->next = prev;
	prev = curr;
	curr = tmp;
	}
	head->next = reverse(curr, k);
	return prev;
	}
	};

view raw Reverse Nodes in k-Group_recursion.cpp hosted with ❤ by GitHub

第二种就是循环，每次reverse一个长度为k的子链表，当前的尾巴连向右边新reverse之后的头节点。除此之外因为新的linkedlist的head节点和以前可能不一样，我们需要在左端用一个helper节点来帮我们keep track of新的头结点。时间O(N)，常数空间，代码如下：

	/**
	* 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) {
	if(k <= 1 || !head)return head;
	ListNode* helper = new ListNode(-1);
	helper->next = head;
	ListNode* start = helper, *end = helper;
	while(start->next)
	{
	int i = k;
	while(i-- > 0 && end)end = end->next;
	if(!end)break;
	ListNode* tail = start->next;
	start->next = reverse(start->next, end);
	start = tail;
	end = tail;
	}
	return helper->next;
	}
	private:
	ListNode* reverse(ListNode* start, ListNode* end)
	{
	ListNode* curr = start, *next = start->next;
	curr->next = end->next;
	while(curr != end)
	{
	auto temp = next->next;
	next->next = curr;
	curr = next;
	next = temp;
	}
	return end;
	}
	};

view raw Reverse Nodes in k-Group_iteratively.cpp hosted with ❤ by GitHub