K 个一组翻转链表

发表于

算法分类： LinkedList

url：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

​

题目：K 个一组翻转链表

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
26
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

 

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

 

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

​

Java解法

1
2


​

Python解法

1
2


Go解法

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package main

import "fmt"

func main() {
	a := &ListNode {
		Val : 1,
	}
	b := &ListNode {
		Val : 2,
	}
	c := &ListNode {
		Val : 3,
	}
	d := &ListNode {
		Val : 4,
	}
	e := &ListNode {
		Val : 5,
	}
	a.Next = b
	b.Next = c
	c.Next = d
	d.Next = e
	e.Next = nil

	head := reverseKGroup(a, 2)
	//head := a
	for head != nil {
		fmt.Print(head.Val)
		head = head.Next
	}
}

/**
 * K 个一组翻转链表
 * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 */

type ListNode struct {
	Val int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	cur := head
	for i := 1; i < k && cur != nil; i++ {
		cur = cur.Next
	}

	if cur == nil {
		return head
	}
	next := cur.Next
	cur.Next = nil
	cur = reverseList(head)
	head.Next = reverseKGroup(next, k)
	return cur
}

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var next *ListNode
	h := head
	pre := head
	cur := head.Next
	for cur != nil {
		next = cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	h.Next = nil
	head = pre
	return pre
}

image-20201102235821468