LinkedList - 25. Reverse Nodes in k-Group

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its 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.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

思路：

题目意思是每k个节点翻转一次链表，如果节点不足k个，就不翻转，这是一个简单的实现题，运用递归的思想，找到翻转链表的起始点，然后翻转k个节点。难点就在于递归到终止条件，需要返回给上层调用栈的是已经反转的链表的head，作为上层反转的尾节点。然后就是简单的单链表翻转了。
所以可以先用一个计数器，来记录整个链表需要翻转的所有节点，把数据压入栈中，递归终止条件就只找到了链表尾，从最后一节k个节点，往上return进行翻转。

代码：

golang:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 递归求解，递归出口是找到翻转后的链表的头节点返回给外层调用
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil { // 节约时间
        return head
    }
    
    var size = 0
    var cur = head
    for cur != nil && size < k {
        cur = cur.Next
        size++
    }
    
    if size == k {
        newHead := reverseKGroup(cur, k)
        // revese [head, cur]
        for size > 0 {
            temp := head.Next
            head.Next = newHead
            newHead = head
            head = temp
            size--
        }
        return newHead
    }
    
    // 已经在上面对head做了校验，这里其实走不到
    return head
}

// 使用数组存储链表值来翻转
func reverseKGroup2(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    var counter = 0
    var cur = head
    var start = head
    var arr = make([]int, k)
    for cur != nil {
        if counter == 0 {
            start = cur
        }
        // 记录需要翻转的值
        arr[counter] = cur.Val
        counter++
        
        if counter == k {
            for i := len(arr) - 1; i >= 0; i-- {
                start.Val = arr[i]
                start = start.Next
            }
            counter = 0
        }
        cur = cur.Next
    }
    
    return head
}