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 <= 105In #2074 Reverse Nodes in Even Length Groups, the linked list is divided into groups whose sizes increase sequentially (1, 2, 3, 4, ...). The main challenge is determining the actual size of each group, since the list may end before a full group is formed. For every group, you first count how many nodes are available and compare that count with the intended group size.
If the group's length is even, you reverse those nodes using the standard linked list reversal technique with pointer manipulation. If the length is odd, you simply keep the nodes in their original order and move to the next group. Careful tracking of the previous group's tail helps reconnect the list correctly after each operation.
This approach works in a single traversal of the list while performing reversals only when needed, making it efficient for large inputs. The algorithm typically runs in O(n) time with O(1) extra space since all operations are done in-place.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Group traversal with conditional in-place reversal | O(n) | O(1) |
Striver
Use these hints if you're stuck. Try solving on your own first.
Consider the list structure ...A → (B → ... → C) → D..., where the nodes between B and C (inclusive) form a group, A is the last node of the previous group, and D is the first node of the next group. How can you utilize this structure?
Suppose you have B → ... → C reversed (because it was of even length) so that it is now C → ... → B. What references do you need to fix so that the transitions between the previous, current, and next groups are correct?
A.next should be set to C, and B.next should be set to D.
Once the current group is finished being modified, you need to find the new A, B, C, and D nodes for the next group. How can you use the old A, B, C, and D nodes to find the new ones?
The new A is either the old B or old C depending on if the group was of even or odd length. The new B is always the old D. The new C and D can be found based on the new B and the next group's length.
You can set the initial values of A, B, C, and D to A = null, B = head, C = head, D = head.next. Repeat the steps from the previous hints until D is null.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of linked list manipulation problems like this appear frequently in FAANG and other top tech interviews. Interviewers often test a candidate's ability to manage pointers, segment lists, and perform in-place reversals.
A singly linked list is the core data structure used in this problem. Efficient pointer manipulation allows you to reverse sections of the list in-place without extra memory. This makes linked list reversal techniques essential for solving the problem efficiently.
The optimal approach is to traverse the linked list while forming groups of increasing sizes (1, 2, 3, ...). For each group, count the actual number of nodes and reverse the nodes only if the length is even. This can be done with in-place pointer manipulation for O(n) time and O(1) space.
The intended group size may be larger than the remaining nodes in the list near the end. Counting the actual nodes ensures the algorithm correctly determines whether the group length is even or odd before deciding to reverse it.