# 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?

## 解析

給定一個單向鏈結串列 list 還有一個整數 k

要求寫一個演算法把每 k 個一組的結點做反序

作法一：

先用一個指標陣列把每個走訪過的結點都存起來

然後算出 nLen/k

每次取出 k個做反向

這樣空間複雜度跟時間複雜度都是 O(n)

作法二：

如果依照順序，每次把新的結點放在前一個結點的的前面

這樣結果也會是反序

要這樣做必須每次紀錄上一次走訪到的結點

作法是先算出 nLen/k

也就是最多要處理 nLen/k * k個結點

每次針對 k個結點做反向

## 程式碼- 作法一

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

```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
nLen := 0
cur := head
for cur != nil {
nLen++
cur = cur.Next
}
if nLen <= 1 || k == 1 {
return head
}
m := nLen / k
max := m * k
cur = head
var tail, preTail, prevHead *ListNode
startCount := 0
for startCount < max {
cur, tail, prevHead, startCount = ReverseKNode(cur, startCount, k)
if startCount == k {
head = prevHead
}
if preTail != nil {
preTail.Next = prevHead
}
preTail = tail
}
if cur != nil {
tail.Next = cur
}
return head
}
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
}
func Transverse(head *ListNode) {
cur := head
for cur != nil {
log.Printf("%v->", cur.Val)
cur = cur.Next
}
log.Println()
}
```

## 困難點

- 因為是單向鏈結，所以要反序必須要紀錄每一個前一個結點
- 要重複 nLen/k 次反序
- 每次要紀錄上一次的tail, head 必須知道如何接續

## Solve Point

- Understand what problem would like to solve
- Analysis Complexity