25. Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/
Hard
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 <= 50000 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory space?
Problem
Given a linked list, group nodes in sets of k and reverse each group’s internal elements. If the total number of remaining nodes is less than k, don’t reverse them. Return the reversed result.
Approach
- Group every k elements and find the tail element of each group.
- Reverse the internal elements of the group.
- Update the head and tail of the group.
Source Code
func reverseKGroup(head *ListNode, k int) *ListNode {
// 1. grouping and find head and tail of group
// 2. reverse this group
// 3. update head and tail
sentinal := &ListNode{}
last := sentinal
for head != nil {
// 1. grouping and find head and tail of group
end := findEnd(head, k)
if end == nil {
break
}
nextGroupHead := end.Next
// 2. reverse this group
reverseLinkedList(head, nextGroupHead)
// 3. update head and tail
last.Next = end
head.Next = nextGroupHead
last = head
head = nextGroupHead
}
return sentinal.Next
}
func findEnd(head *ListNode, k int) *ListNode {
for head != nil {
k--
if k == 0 {
return head
}
head = head.Next
}
return nil
}
func reverseLinkedList(head, tail *ListNode) {
last := head
head = head.Next
for head != tail {
headNext := head.Next
head.Next = last
last = head
head = headNext
}
}
Closing
Do you have a better or simpler solution?
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
