LeetCode_25: Reverse Nodes in k-Group

# 引言

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

# 题目大意

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

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

• 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

# 题解

# 一句话题解

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

# 复杂度

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

空间复杂度 O(1)

# AC代码

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
}