{"id":8712,"date":"2021-11-15T10:52:13","date_gmt":"2021-11-15T18:52:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8712"},"modified":"2021-11-15T11:08:56","modified_gmt":"2021-11-15T19:08:56","slug":"leetcode-2074-reverse-nodes-in-even-length-groups","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-2074-reverse-nodes-in-even-length-groups\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2074. Reverse Nodes in Even Length Groups"},"content":{"rendered":"\n<p>You are given the&nbsp;<code>head<\/code>&nbsp;of a linked list.<\/p>\n\n\n\n<p>The nodes in the linked list are&nbsp;<strong>sequentially<\/strong>&nbsp;assigned to&nbsp;<strong>non-empty<\/strong>&nbsp;groups whose lengths form the sequence of the natural numbers (<code>1, 2, 3, 4, ...<\/code>). The&nbsp;<strong>length<\/strong>&nbsp;of a group is the number of nodes assigned to it. In other words,<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The&nbsp;<code>1<sup>st<\/sup><\/code>&nbsp;node is assigned to the first group.<\/li><li>The&nbsp;<code>2<sup>nd<\/sup><\/code>&nbsp;and the&nbsp;<code>3<sup>rd<\/sup><\/code>&nbsp;nodes are assigned to the second group.<\/li><li>The&nbsp;<code>4<sup>th<\/sup><\/code>,&nbsp;<code>5<sup>th<\/sup><\/code>, and&nbsp;<code>6<sup>th<\/sup><\/code>&nbsp;nodes are assigned to the third group, and so on.<\/li><\/ul>\n\n\n\n<p>Note that the length of the last group may be less than or equal to&nbsp;<code>1 + the length of the second to last group<\/code>.<\/p>\n\n\n\n<p><strong>Reverse<\/strong>&nbsp;the nodes in each group with an&nbsp;<strong>even<\/strong>&nbsp;length, and return&nbsp;<em>the<\/em>&nbsp;<code>head<\/code>&nbsp;<em>of the modified linked list<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/10\/25\/eg1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [5,2,6,3,9,1,7,3,8,4]\n<strong>Output:<\/strong> [5,6,2,3,9,1,4,8,3,7]\n<strong>Explanation:<\/strong>\n- The length of the first group is 1, which is odd, hence no reversal occurrs.\n- The length of the second group is 2, which is even, hence the nodes are reversed.\n- The length of the third group is 3, which is odd, hence no reversal occurrs.\n- The length of the last group is 4, which is even, hence the nodes are reversed.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/10\/25\/eg2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [1,1,0,6]\n<strong>Output:<\/strong> [1,0,1,6]\n<strong>Explanation:<\/strong>\n- The length of the first group is 1. No reversal occurrs.\n- The length of the second group is 2. The nodes are reversed.\n- The length of the last group is 1. No reversal occurrs.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/10\/28\/eg3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [2,1]\n<strong>Output:<\/strong> [2,1]\n<strong>Explanation:<\/strong>\n- The length of the first group is 1. No reversal occurrs.\n- The length of the last group is 1. No reversal occurrs.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [8]\n<strong>Output:<\/strong> [8]\n<strong>Explanation:<\/strong> There is only one group whose length is 1. No reversal occurrs.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The number of nodes in the list is in the range&nbsp;<code>[1, 10<sup>5<\/sup>]<\/code>.<\/li><li><code>0 &lt;= Node.val &lt;= 10<sup>5<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: List<\/strong><\/h2>\n\n\n\n<p>Reuse ReverseList from<a href=\"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-206-reverse-linked-list\/\" data-type=\"post\" data-id=\"2044\"> \u82b1\u82b1\u9171 LeetCode 206. Reverse Linked List<\/a><\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  ListNode* reverseEvenLengthGroups(ListNode* head) {\n    ListNode dummy(0, head);\n    ListNode* prev = &dummy;\n    auto reverse = [](ListNode* head) {     \n      ListNode* prev = nullptr;\n      while (head) {\n        ListNode* next = head->next;\n        head->next = prev;\n        prev = head;\n        head = next;\n      }\n      return prev;\n    };\n    \n    for (int k = 1; head; ++k) {\n      ListNode* tail = head;\n      int l = 1;\n      while (l < k &#038;&#038; tail &#038;&#038; tail->next) {\n        tail = tail->next;\n        ++l;\n      }\n      ListNode* next = tail->next;\n      if (l % 2 == 0) {\n        tail->next = nullptr;\n        prev->next = reverse(head);\n        head->next = next;\n        prev = head;        \n        head = head->next;\n      } else {\n        prev = tail;\n        head = next;\n      }\n    }\n    return dummy.next;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given the&nbsp;head&nbsp;of a linked list. The nodes in the linked list are&nbsp;sequentially&nbsp;assigned to&nbsp;non-empty&nbsp;groups whose lengths form the sequence of the natural numbers (1,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[],"class_list":["post-8712","post","type-post","status-publish","format-standard","hentry","category-list","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8712","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8712"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8712\/revisions"}],"predecessor-version":[{"id":8714,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8712\/revisions\/8714"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8712"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8712"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8712"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}