reverse_k_nodes.go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseList(cur *ListNode, k int) (*ListNode, *ListNode) {
    if cur.Next == nil || k == 1 {
        return cur, cur
    }
    tmp, head := reverseList(cur.Next, k-1)
    tmp.Next = cur
    cur.Next = nil
    return cur, head
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    var ans *ListNode
    var lastTail *ListNode
    
    it, cnt := head, 0
    for it != nil {
        cnt++
        if cnt%k == 0 {
            tmp := it.Next
            tail, newHead := reverseList(head, k)
            if ans == nil {
                ans = newHead
            }
            if lastTail == nil {
                lastTail = tail
            } else {
                lastTail.Next = newHead
                lastTail = tail
            }
            tail.Next = tmp
            head = tmp
            it = tmp
        } else {
            it = it.Next
        }
    }
    
    return ans
}