前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的25题。
问题描述
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 1:
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
分析：
开始没理解题目的意思，以为是不足的也需要逆转
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
if nil == head || k == 1 {
return head
}
var prev, back *ListNode
prev = head
ret, p, q := head, head, head.Next
count := 1
for ret.Next != nil && count < k {
ret = ret.Next
count++
}
count = 1
for nil != p && nil != q {
if count == k {
p, q = q, q.Next
count = 1
back = p
for back.Next != nil && count < k {
back = back.Next
count++
}
prev.Next = back
count = 1
prev = p
} else {
q, q.Next, p = q.Next, p, q
count++
}
}
prev.Next = nil
return ret
}
重新写的
func reverseKGroup(head *ListNode, k int) *ListNode {
root := &ListNode{0, head}
res := root
eleCounts := 0
var node *ListNode
for temp := head; nil != temp; temp = temp.Next {
eleCounts++
}
for eleCounts >= k {
for j := 0; j < k-1; j++ {
node = root.Next
root.Next = head.Next
head.Next = head.Next.Next
root.Next.Next = node
}
root = head
head = head.Next
eleCounts -= k
}
return res.Next
}
执行用时: 44 ms, 在Reverse Nodes in k-Group的Go提交中击败了2.36% 的用户
内存消耗: 3.6 MB, 在Reverse Nodes in k-Group的Go提交中击败了0.00% 的用户
效率太低
官方给出的一个8ms的示例代码。用到递归
func reverseKGroup(head *ListNode, k int) *ListNode {
tmpNode := head
for i := 0; i < k; i++ {
if tmpNode == nil {
return head
}
tmpNode = tmpNode.Next
}
tmpNode = head
for i := 0; i < k-1; i++ {
// move N2 to head
N2 := tmpNode.Next
tmpNode.Next, head, N2.Next = N2.Next, N2, head
}
tmpNode.Next = reverseKGroup(tmpNode.Next, k)
return head
}
总结：
勤思考。
结语
不管怎么样好好加油。
