leetcode25 K个一组反转链表

题目

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

解析

大致的思路是遍历到符合的位置后，调用反转链表改进后的代码，然后在递归处理后面的部分

上面的图对应的代码如下：

func reverseKGroup(head *ListNode, k int) *ListNode {
	cur := head
	for i := 0; i < k; i++ {
		if cur == nil {
			return head // 不够K个，就不反转了
		}
		cur = cur.Next
	}
	newHead := reverse(head, cur) // 注意这里cur是从和head开始的，所以会多走了一位。第一次返回的newHead就是结果的头结点。在反转后，head所在的位置不变（还是开头，但此时已经变成了反转后的结尾，看上图，其next正好连接下一段链表）
	head.Next = reverseKGroup(cur, k)
    return newHead
	
}

func reverse(start, end *ListNode) *ListNode {
	var pre *ListNode
	cur := start
	for cur != end {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25