2196. Reverse Nodes In Even Length Groups¶

LeetCode Problem View on GitHub

2196. Reverse Nodes in Even Length Groups

Medium

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

Solution¶

/**
 * 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) {
        ListNode temp = head;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> tempNodes = new ArrayList<>();
        int req = 1;
        while (temp != null) {
            if (tempNodes.size() == req) {
                req++;
                res.add(new ArrayList<>(tempNodes));
                tempNodes.clear();
            }
            tempNodes.add(temp.val);
            temp = temp.next;
        }
        res.add(new ArrayList<>(tempNodes)); 
        for (ArrayList<Integer> curr : res) {
            if (curr.size() % 2 == 0) 
                Collections.reverse(curr);
        }
        ListNode ans = null;
        for (int i = res.size() - 1; i >= 0; i--) {
            ArrayList<Integer> current = res.get(i);
            for (int j = current.size() - 1; j >= 0; j--) {
                ans = addNode(ans, res.get(i).get(j));
            }
        }    
        return ans;
    }
    private ListNode addNode(ListNode head, int val) {
        ListNode current = new ListNode(val);
        if (head == null) {
            return current;
        }
        else {
            current.next = head;
            head = current;
            return head;
        } 
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here