Reverse Nodes in Even-Length Groups — Group Counting
Advertisement
Problem 239 · Reverse Nodes in Even Length Groups
Difficulty: Medium · Pattern: Group Reversal
Groups are sized 1, 2, 3, 4, ... Reverse each group that has an even number of nodes.
Solutions
# Python
def reverseEvenLengthGroups(head):
prev = head # prev group's last node
group_len = 2 # current expected group size
while prev.next:
# Count actual nodes in this group
node = prev
count = 0
while node.next and count < group_len:
node = node.next; count += 1
group_len += 1
if count % 2 == 0:
# Reverse 'count' nodes starting from prev.next
tail = prev.next
cur = tail.next
for _ in range(count - 1):
tail.next = cur.next
cur.next = prev.next
prev.next = cur
cur = tail.next
prev = node
return head
// Java
public ListNode reverseEvenLengthGroups(ListNode head) {
ListNode prev = head;
for (int groupLen = 2; prev.next != null; groupLen++) {
ListNode node = prev; int count = 0;
while (node.next != null && count < groupLen) { node = node.next; count++; }
if (count % 2 == 0) {
ListNode tail = prev.next, cur = tail.next;
for (int i = 0; i < count-1; i++) {
tail.next = cur.next; cur.next = prev.next; prev.next = cur; cur = tail.next;
}
}
prev = node;
}
return head;
}
Complexity
- Time: O(n)
- Space: O(1)
Advertisement