Reverse Nodes in k-Group

1. Problem Description

Reverse the nodes of the given linked list in groups of k and return the resulting list. If the number of nodes is not a multiple of k, leave the remaining nodes at the end unchanged. You may not change node values; only the nodes themselves may be relinked. The required space complexity is O(1).

2. Approach

1. Temporarily Store Groups in Arrays
   • Traverse the linked list
     • Divide it into groups of n nodes
   • Reverse each group
   • Traverse the groups and build the linked list
   • This implementation creates new nodes and uses O(N) extra space, so it does not satisfy the problem’s O(1) extra-space requirement or the constraint that only node links may be changed; it is retained only as a historical implementation
2. Reverse While Traversing
3. 

3. Implementation

3.1. Temporarily Store Groups in Arrays

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k <= 1 {
        return head
    }

    var groups [][]int
    var group []int
    current := head
    i := 0
    for {
        if current == nil {
            if len(group) > 0 {
                groups = append(groups, group)
                group = make([]int, 0) 
            }
            break
        }

        group = append(group, current.Val)
        i++
        if i % k == 0 {
            groups = append(groups, group)
            group = make([]int, 0)
        }
        current = current.Next
    }

    for _, group := range groups {
        if len(group) == k {
            reverse(group)
        }
    }

    dummyHead := &ListNode{}
    current = dummyHead
    for _, group := range groups {
        for _, val := range group {
            current.Next = &ListNode{Val:val}
            current = current.Next
        }
    }
    return dummyHead.Next
}

func reverse(group []int) {
    i := 0
    j := len(group)-1
    for i < j {
        group[i],group[j] = group[j], group[i]
        i++
        j--
    }
}

3.2. Reverse While Traversing

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

type KNodeGroup struct {
    head *ListNode
    tail *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummyHead := &ListNode{}
    d := dummyHead
    current := head
    for {
        kGroup,ok := findKGroupHead(current, k)
        if ok {
            current = kGroup.tail.Next
            d.Next = reverseList(kGroup.head, k)
            d = kGroup.head
        }else {
            d.Next = current
            break
        }
       
    }
    return dummyHead.Next
}

func findKGroupHead(head *ListNode, k int)(*KNodeGroup,bool) {
    count := 0
    current := head
    for current != nil {
        count++
        if count == k {
            return &KNodeGroup{head:head, tail:current}, true
        }
        current = current.Next
    }
    return nil, false
}

func reverseList(head *ListNode, k int)*ListNode {
    var pre *ListNode
	current := head
	var next *ListNode
	for i := 0; i < k; i++ {
		next = current.Next
		current.Next = pre
		pre = current
		current = next
	}
 
	return pre
}

3.3. Other

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 *
 * @param head ListNode
 * @param k integer
 * @return ListNode
 */
//{1,2,3,4,5},2
func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 1 {
		return head
	}

	res := &ListNode{}
	res.Next = head

	pre := res
	cur := head
	var tmp *ListNode
	length := 0
	for head != nil {
		length++
		head = head.Next
	}


	for i := 0; i < length/k; i++ {
		for j := 1; j < k; j++ {
			tmp = cur.Next
			cur.Next = tmp.Next
			tmp.Next = pre.Next
			pre.Next = tmp
		}

		pre = cur
		cur = cur.Next
	}

	return res.Next
}

4. References

• Reverse Nodes in k-Group - NowCoder
• 25. Reverse Nodes in k-Group - LeetCode