# golang_reverse_node_k_group

Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return the modified list.

`k` is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of `k` then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

## Examples

Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return the modified list.

`k` is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of `k` then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1: ``````Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

``````

Example 2: ``````Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

``````

Constraints:

• The number of nodes in the list is `n`.
• `1 <= k <= n <= 5000`
• `0 <= Node.val <= 1000`

Follow-up: Can you solve the problem in `O(1)` extra memory space?

## 程式碼- 作法一

```/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
arr := []*ListNode{}
for cur != nil {
arr = append(arr, cur)
cur = cur.Next
}
nLen := len(arr)
if nLen <= 1 || k == 1 {
}
m := nLen / k
for idx := 0; idx < m; idx++ {
ReverseList(&arr, idx*k, (idx+1)*k-1, k)
}
}

func ReverseList(arr *[]*ListNode, start int, end int, step int) {
temp := *arr
for idx := end; idx >= start; idx-- {
if idx-1 >= 0 {
temp[idx].Next = temp[idx-1]
}
}
if start+2*step-1 < len(temp) {
temp[start].Next = temp[start+2*step-1]
} else {
if end+1 < len(temp) {
temp[start].Next = temp[end+1]
} else {
temp[start].Next = nil
}
}
}```

## 程式碼-作法2

```/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
nLen := 0
for cur != nil {
nLen++
cur = cur.Next
}
if nLen <= 1 || k == 1 {
}
m := nLen / k
max := m * k
startCount := 0
for startCount < max {
cur, tail, prevHead, startCount = ReverseKNode(cur, startCount, k)
if startCount == k {
}
if preTail != nil {
}
preTail = tail
}
if cur != nil {
tail.Next = cur
}
}

func ReverseKNode(startNode *ListNode, startCount int, step int) (*ListNode, *ListNode, *ListNode, int) {
var tail, prev *ListNode
cur := startNode
count := startCount
max := startCount + step
for count < max {
if tail == nil {
tail = cur
}
if prev == nil {
prev = cur
cur = cur.Next
} else {
temp := prev
prev = cur
cur = cur.Next
prev.Next = temp
}
count++
}
tail.Next = nil
return cur, tail, prev, count
}
for cur != nil {
log.Printf("%v->", cur.Val)
cur = cur.Next
}
log.Println()
}```

## 困難點

1. 因為是單向鏈結，所以要反序必須要紀錄每一個前一個結點
2. 要重複 nLen/k 次反序