0025.K 个一组翻转链表

方法一：递归

时间复杂度 $O(n)$，空间复杂度 $O(\log _k n)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	start, end := head, head
	for i := 0; i < k; i++ {
		if end == nil {
			return head
		}
		end = end.Next
	}
	res := reverse(start, end)
	start.Next = reverseKGroup(end, k)
	return res
}

func reverse(start, end *ListNode) *ListNode {
	var pre *ListNode = nil
	for start != end {
		tmp := start.Next
		start.Next, pre = pre, start
		start = tmp
	}
	return pre
}

方法二：迭代

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	var dummy *ListNode = &ListNode{}
	p, cur := dummy, head
	for cur != nil {
		start := cur
		for i := 0; i < k; i++ {
			if cur == nil {
				p.Next = start
				return dummy.Next
			}
			cur = cur.Next
		}
		p.Next, p = reverse(start, cur), start
	}
	return dummy.Next
}

func reverse(start, end *ListNode) *ListNode {
	var pre *ListNode = nil
	for start != end {
		tmp := start.Next
		start.Next, pre = pre, start
		start = tmp
	}
	return pre
}