LeetCode_25: Reverse Nodes in k-Group - LeetCode

# 引言

题目链接：https://leetcode.com/problems/reverse-nodes-in-k-group/

给定一个链表，一次反转链表的 k 个节点 (每 k 个节点翻转一次), 最后返回修改后的列表。

Hint: k 是正整数，并且小于或等于链表的长度。如果节点数不是 k 的倍数，那么最后的剩余节点应该保持不变。

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

这题算是 24 题 Swap Nodes in Pairs 的进阶版本。使用快慢指针，先行指针先走 k 步，就地转置慢指针与快指针之间的节点，最后处理整个翻转链，重复这个过程直至结束

时间复杂度 O(kn) , k 是需要翻转的区间长度

空间复杂度 O(1)

c++ 版本

	/**
	* 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)
	{
	ListNode *ret = new ListNode(-1);
	ret->next = head;
	ListNode *fast = ret;
	ListNode *slow = ret;
	ListNode tmp1, tmp2;
	while (nullptr != fast && nullptr != fast->next)
	{
	int n = k;
	while (n && nullptr != fast->next)
	{
	fast = fast->next;
	--n;
	}
	if (n > 0)
	{
	break;
	}
	tmp1 = fast->next;
	tmp2 = slow->next;
	reverseIntervalList(slow->next, fast);
	slow->next->next = tmp1;
	slow->next = fast;
	slow = fast = tmp2;
	}
	return ret->next;
	}

	private:
	void reverseIntervalList(ListNode begin, ListNode end)
	{
	ListNode *pre = begin;
	ListNode *cur = begin->next;
	ListNode *tmp;
	while (pre != end)
	{
	tmp = cur->next;
	cur->next = pre;
	pre = cur;
	cur = tmp;
	}
	}
	};

go 版本

	/**
	* Definition for singly-linked list.
	* type ListNode struct {
	* Val int
	* Next *ListNode
	* }
	*/


	func reverseIntervalList(begin, end *ListNode) {
	pre, cur := begin, begin.Next
	var tmp *ListNode
	for pre != end {
	tmp = cur.Next
	cur.Next = pre
	pre = cur
	cur = tmp
	}
	}
	func reverseKGroup(head ListNode, k int) ListNode {
	ret := &ListNode{-1, nil}
	ret.Next = head
	fast, slow := ret, ret
	var tmp1, tmp2 *ListNode
	for nil != fast && nil != fast.Next {
	n := k
	for n > 0 && nil != fast.Next {
	fast = fast.Next
	n--
	}
	if n > 0 {
	break
	}
	tmp1 = fast.Next
	tmp2 = slow.Next
	reverseIntervalList(slow.Next, fast)
	slow.Next.Next = tmp1
	slow.Next = fast
	slow, fast = tmp2, tmp2
	}
	return ret.Next
	}