2074

2074. 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 occurrs.
- 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 occurrs.
- 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 occurrs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 1. No reversal occurrs.

Example 3:

Input: head = [2,1]
Output: [2,1]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the last group is 1. No reversal occurrs.

Example 4:

Input: head = [8]
Output: [8]
Explanation: There is only one group whose length is 1. No reversal occurrs.

 

Constraints:

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

Similar Questions:

• Reverse Nodes in k-Group (Hard)
• Reverse Linked List (Easy)

Solution 1. Two Pass

// OJ: https://leetcode.com/problems/reverse-nodes-in-even-length-groups/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    int getLength(ListNode *head) {
        int len = 0;
        for (; head; head = head->next) ++len;
        return len;
    }
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        ListNode dummy, *tail = &dummy;
        for (int i = 1, total = getLength(head); head; ++i) {
            int len = min(total, i); // the length of the current section
            ListNode *newTail = NULL; // The new tail if we need to reverse the current section
            for (int j = 0; j < len && head; ++j) {
                auto p = head;
                head = head->next;
                if (len % 2) { // direct append
                    tail->next = p;
                    tail = p;
                } else { // append in reverse order
                    if (newTail == NULL) newTail = p;
                    p->next = tail->next; 
                    tail->next = p;
                }
            }
            if (newTail) tail = newTail;
            total -= len;
        }
        tail->next = NULL;
        return dummy.next;
    }
};

Discuss

https://leetcode.com/problems/reverse-nodes-in-even-length-groups/discuss/1576917/C%2B%2B-Two-Pass