LeetCode-in-All

25. Reverse Nodes in k-Group

Hard

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.

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]

Example 3:

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

Output: [1,2,3,4,5]

Example 4:

Input: head = [1], k = 1

Output: [1]

Constraints:

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

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

Solution

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 * 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 || k == 1 {
		return head
	}
	j := 0
	len := head
	// Loop to check the length of the linked list. If the list is less than k, return as it is.
	for j < k {
		if len == nil {
			return head
		}
		len = len.Next
		j++
	}
	// Apply reverse linked list logic.
	c := head
	var n *ListNode
	var prev *ListNode
	i := 0
	// Traverse the while loop for k times to reverse the nodes in k groups.
	for i != k {
		n = c.Next
		c.Next = prev
		prev = c
		c = n
		i++
	}
	// head points to the first node of the k group, which now points to the next k group.
	// Recurse for the remaining linked list.
	head.Next = reverseKGroup(n, k)
	return prev
}

This site is open source. Improve this page.