2074. Reverse Nodes in Even Length Groups LeetCode Solution
In this guide, you will get 2074. Reverse Nodes in Even Length Groups LeetCode Solution with the best time and space complexity. The solution to Reverse Nodes in Even Length Groups problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Reverse Nodes in Even Length Groups solution in C++
- Reverse Nodes in Even Length Groups solution in Java
- Reverse Nodes in Even Length Groups solution in Python
- Additional Resources
Problem Statement of Reverse Nodes in Even Length Groups
You are given the head of a linked list.
The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, …). The length of a group is the number of nodes assigned to it. In other words,
The 1st node is assigned to the first group.
The 2nd and the 3rd nodes are assigned to the second group.
The 4th, 5th, and 6th nodes are assigned to the third group, and so on.
Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.
Reverse the nodes in each group with an even length, and return the head of the modified linked list.
Example 1:
Input: head = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
– The length of the first group is 1, which is odd, hence no reversal occurs.
– The length of the second group is 2, which is even, hence the nodes are reversed.
– The length of the third group is 3, which is odd, hence no reversal occurs.
– The length of the last group is 4, which is even, hence the nodes are reversed.
Example 2:
Input: head = [1,1,0,6]
Output: [1,0,1,6]
Explanation:
– The length of the first group is 1. No reversal occurs.
– The length of the second group is 2. The nodes are reversed.
– The length of the last group is 1. No reversal occurs.
Example 3:
Input: head = [1,1,0,6,5]
Output: [1,0,1,5,6]
Explanation:
– The length of the first group is 1. No reversal occurs.
– The length of the second group is 2. The nodes are reversed.
– The length of the last group is 2. The nodes are reversed.
Constraints:
The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 105
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1)
2074. Reverse Nodes in Even Length Groups LeetCode Solution in C++
class Solution {
public:
ListNode* reverseEvenLengthGroups(ListNode* head) {
// prev -> (head -> ... -> tail) -> next -> ...
ListNode dummy(0, head);
ListNode* prev = &dummy;
ListNode* tail = head;
ListNode* next = head->next;
int groupLength = 1;
while (true) {
if (groupLength % 2 == 1) {
prev->next = head;
prev = tail;
} else {
tail->next = nullptr;
prev->next = reverse(head);
// Prev -> (tail -> ... -> head) -> next -> ...
head->next = next;
prev = head;
}
if (next == nullptr)
break;
head = next;
const auto [theTail, theLength] = getTailAndLength(head, groupLength + 1);
tail = theTail;
next = tail->next;
groupLength = theLength;
}
return dummy.next;
}
private:
pair<ListNode*, int> getTailAndLength(ListNode* head, int groupLength) {
int length = 1;
ListNode* tail = head;
while (length < groupLength && tail->next) {
tail = tail->next;
++length;
}
return {tail, length};
}
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
while (head != nullptr) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
};
/* code provided by PROGIEZ */2074. Reverse Nodes in Even Length Groups LeetCode Solution in Java
class Solution {
public ListNode reverseEvenLengthGroups(ListNode head) {
// prev -> (head -> ... -> tail) -> next -> ...
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
ListNode tail = head;
ListNode next = head.next;
int groupLength = 1;
while (true) {
if (groupLength % 2 == 1) {
prev.next = head;
prev = tail;
} else {
tail.next = null;
prev.next = reverse(head);
// Prev -> (tail -> ... -> head) -> next -> ...
head.next = next;
prev = head;
}
if (next == null)
break;
head = next;
Pair<ListNode, Integer> res = getTailAndLength(head, groupLength + 1);
tail = res.getKey();
next = tail.next;
groupLength = res.getValue();
}
return dummy.next;
}
private Pair<ListNode, Integer> getTailAndLength(ListNode head, int groupLength) {
int length = 1;
ListNode tail = head;
while (length < groupLength && tail.next != null) {
tail = tail.next;
++length;
}
return new Pair<>(tail, length);
}
ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
// code provided by PROGIEZ2074. Reverse Nodes in Even Length Groups LeetCode Solution in Python
class Solution:
def reverseEvenLengthGroups(self, head: ListNode | None) -> ListNode | None:
# prev -> (head -> ... -> tail) -> next -> ...
dummy = ListNode(0, head)
prev = dummy
tail = head
next = head.next
groupLength = 1
def getTailAndLength(head: ListNode | None, groupLength: int) -> tuple[ListNode | None, int]:
length = 1
tail = head
while length < groupLength and tail.next:
tail = tail.next
length += 1
return tail, length
def reverse(head: ListNode | None) -> ListNode | None:
prev = None
while head:
next = head.next
head.next = prev
prev = head
head = next
return prev
while True:
if groupLength % 2 == 1:
prev.next = head
prev = tail
else:
tail.next = None
prev.next = reverse(head)
# Prev -> (tail -> ... -> head) -> next -> ...
head.next = next
prev = head
if not next:
break
head = next
tail, length = getTailAndLength(head, groupLength + 1)
next = tail.next
groupLength = length
return dummy.next
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.