Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Move from brute-force thinking to an efficient approach using linked list strategy.
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,
1st node is assigned to the first group.2nd and the 3rd nodes are assigned to the second group.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:
[1, 105].0 <= Node.val <= 105Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Linked List
[5,2,6,3,9,1,7,3,8,4]
[1,1,0,6]
[1,1,0,6,5]
reverse-nodes-in-k-group)reverse-linked-list)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2074: Reverse Nodes in Even Length Groups
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseEvenLengthGroups(ListNode head) {
int n = 0;
for (ListNode t = head; t != null; t = t.next) {
++n;
}
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
int l = 1;
for (; (1 + l) * l / 2 <= n && prev != null; ++l) {
if (l % 2 == 0) {
ListNode node = prev.next;
prev.next = reverse(node, l);
}
for (int i = 0; i < l && prev != null; ++i) {
prev = prev.next;
}
}
int left = n - l * (l - 1) / 2;
if (left > 0 && left % 2 == 0) {
ListNode node = prev.next;
prev.next = reverse(node, left);
}
return dummy.next;
}
private ListNode reverse(ListNode head, int l) {
ListNode prev = null;
ListNode cur = head;
ListNode tail = cur;
int i = 0;
while (cur != null && i < l) {
ListNode t = cur.next;
cur.next = prev;
prev = cur;
cur = t;
++i;
}
tail.next = cur;
return prev;
}
}
// Accepted solution for LeetCode #2074: Reverse Nodes in Even Length Groups
// Auto-generated Go example from java.
func exampleSolution() {
}
// Reference (java):
// // Accepted solution for LeetCode #2074: Reverse Nodes in Even Length Groups
// /**
// * Definition for singly-linked list.
// * public class ListNode {
// * int val;
// * ListNode next;
// * ListNode() {}
// * ListNode(int val) { this.val = val; }
// * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
// class Solution {
// public ListNode reverseEvenLengthGroups(ListNode head) {
// int n = 0;
// for (ListNode t = head; t != null; t = t.next) {
// ++n;
// }
// ListNode dummy = new ListNode(0, head);
// ListNode prev = dummy;
// int l = 1;
// for (; (1 + l) * l / 2 <= n && prev != null; ++l) {
// if (l % 2 == 0) {
// ListNode node = prev.next;
// prev.next = reverse(node, l);
// }
// for (int i = 0; i < l && prev != null; ++i) {
// prev = prev.next;
// }
// }
// int left = n - l * (l - 1) / 2;
// if (left > 0 && left % 2 == 0) {
// ListNode node = prev.next;
// prev.next = reverse(node, left);
// }
// return dummy.next;
// }
//
// private ListNode reverse(ListNode head, int l) {
// ListNode prev = null;
// ListNode cur = head;
// ListNode tail = cur;
// int i = 0;
// while (cur != null && i < l) {
// ListNode t = cur.next;
// cur.next = prev;
// prev = cur;
// cur = t;
// ++i;
// }
// tail.next = cur;
// return prev;
// }
// }
# Accepted solution for LeetCode #2074: Reverse Nodes in Even Length Groups
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(head, l):
prev, cur, tail = None, head, head
i = 0
while cur and i < l:
t = cur.next
cur.next = prev
prev = cur
cur = t
i += 1
tail.next = cur
return prev
n = 0
t = head
while t:
t = t.next
n += 1
dummy = ListNode(0, head)
prev = dummy
l = 1
while (1 + l) * l // 2 <= n and prev:
if l % 2 == 0:
prev.next = reverse(prev.next, l)
i = 0
while i < l and prev:
prev = prev.next
i += 1
l += 1
left = n - l * (l - 1) // 2
if left > 0 and left % 2 == 0:
prev.next = reverse(prev.next, left)
return dummy.next
// Accepted solution for LeetCode #2074: Reverse Nodes in Even Length Groups
/**
* [2074] 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 1^st node is assigned to the first group.
* The 2^nd and the 3^rd nodes are assigned to the second group.
* The 4^th, 5^th, and 6^th 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:
* <img alt="" src="https://assets.leetcode.com/uploads/2021/10/25/eg1.png" style="width: 699px; height: 124px;" />
* 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:
* <img alt="" src="https://assets.leetcode.com/uploads/2021/10/25/eg2.png" style="width: 284px; height: 114px;" />
* 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:
* <img alt="" src="https://assets.leetcode.com/uploads/2021/11/17/ex3.png" style="width: 348px; height: 114px;" />
* 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, 10^5].
* 0 <= Node.val <= 10^5
*
*/
pub struct Solution {}
use crate::util::linked_list::{ListNode, to_list};
// problem: https://leetcode.com/problems/reverse-nodes-in-even-length-groups/
// discuss: https://leetcode.com/problems/reverse-nodes-in-even-length-groups/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn reverse_even_length_groups(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
Some(Box::new(ListNode::new(0)))
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[ignore]
fn test_2074_example_1() {
let head = linked![5, 2, 6, 3, 9, 1, 7, 3, 8, 4];
let result = linked![5, 6, 2, 3, 9, 1, 4, 8, 3, 7];
assert_eq!(Solution::reverse_even_length_groups(head), result);
}
#[test]
#[ignore]
fn test_2074_example_2() {
let head = linked![1, 1, 0, 6];
let result = linked![1, 0, 1, 6];
assert_eq!(Solution::reverse_even_length_groups(head), result);
}
#[test]
#[ignore]
fn test_2074_example_3() {
let head = linked![1, 1, 0, 6, 5];
let result = linked![1, 0, 1, 5, 6];
assert_eq!(Solution::reverse_even_length_groups(head), result);
}
}
// Accepted solution for LeetCode #2074: Reverse Nodes in Even Length Groups
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseEvenLengthGroups(head: ListNode | null): ListNode | null {
let nums = [];
let cur = head;
while (cur) {
nums.push(cur.val);
cur = cur.next;
}
const n = nums.length;
for (let i = 0, k = 1; i < n; i += k, k++) {
// 最后一组， 可能出现不足
k = Math.min(n - i, k);
if (!(k & 1)) {
let tmp = nums.splice(i, k);
tmp.reverse();
nums.splice(i, 0, ...tmp);
}
}
cur = head;
for (let num of nums) {
cur.val = num;
cur = cur.next;
}
return head;
}
Use this to step through a reusable interview workflow for this problem.
Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.
Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.