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
1stnode is assigned to the first group. - The
2ndand the3rdnodes are assigned to the second group. - The
4th,5th, and6thnodes 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
Solution: List
Reuse ReverseList from 花花酱 LeetCode 206. Reverse Linked List
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Solution { public: ListNode* reverseEvenLengthGroups(ListNode* head) { ListNode dummy(0, head); ListNode* prev = &dummy; auto reverse = [](ListNode* head) { ListNode* prev = nullptr; while (head) { ListNode* next = head->next; head->next = prev; prev = head; head = next; } return prev; }; for (int k = 1; head; ++k) { ListNode* tail = head; int l = 1; while (l < k && tail && tail->next) { tail = tail->next; ++l; } ListNode* next = tail->next; if (l % 2 == 0) { tail->next = nullptr; prev->next = reverse(head); head->next = next; prev = head; head = head->next; } else { prev = tail; head = next; } } return dummy.next; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment