Description

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:

1Input: head = [5,2,6,3,9,1,7,3,8,4]
2Output: [5,6,2,3,9,1,4,8,3,7]
3Explanation:
4- The length of the first group is 1, which is odd, hence no reversal occurs.
5- The length of the second group is 2, which is even, hence the nodes are reversed.
6- The length of the third group is 3, which is odd, hence no reversal occurs.
7- The length of the last group is 4, which is even, hence the nodes are reversed.

Example 1

Example 2:

1Input: head = [1,1,0,6]
2Output: [1,0,1,6]
3Explanation:
4- The length of the first group is 1. No reversal occurs.
5- The length of the second group is 2. The nodes are reversed.
6- The length of the last group is 1. No reversal occurs.

Example 2

Example 3:

1Input: head = [1,1,0,6,5]
2Output: [1,0,1,5,6]
3Explanation:
4- The length of the first group is 1. No reversal occurs.
5- The length of the second group is 2. The nodes are reversed.
6- The length of the last group is 2. The nodes are reversed.

Example 3

Constraints:

  • The number of nodes in the list is in the range [1, 10^5].
  • 0 <= Node.val <= 10^5

Solution

Here, we need to reverse only even length groups. If the group has a length of odd number, then we do not need to reverse it. For this we can iterate through the list and in each iteration we track group. First we find the number of nodes in the given group because it is possible that a group may have less number of nodes if it is the last group. So, we always have to check the number of nodes in the group. Once we have the group, if the group is even, we have to reverse it else we keep it as it is.

 1class Solution {
 2    public ListNode reverseEvenLengthGroups(ListNode head) {
 3        int group = 2;
 4        ListNode current = head.next;
 5        ListNode prev = head;
 6        while(current != null) {
 7            ListNode groupCurrent = current;
 8            ListNode groupPrev = prev;
 9            int numNodes = 1;
10            while(current != null && numNodes <= group) {
11                prev = current;
12                current = current.next;
13                numNodes++;
14            }
15            numNodes = numNodes - 1;
16            if(numNodes % 2 == 0) {
17                ListNode newHead = reverse(groupCurrent, Math.min(numNodes, group));
18                groupPrev.next = newHead;
19                prev = groupCurrent;
20            }
21            group++;
22        }
23        return head;
24    }
25
26
27    private ListNode reverse(ListNode head, int count) {
28        ListNode prev = null;
29        ListNode curr = head;
30        ListNode next = null;
31        while(curr != null && count > 0) {
32            next = curr.next;
33            curr.next = prev;
34            prev = curr;
35            curr = next;
36            count--;
37        }
38        head.next = next;
39        return prev;
40    }
41}
  • Time Complexity: O(n)
  • Space Complexity: O(1)