{"id":5484,"date":"2019-08-24T11:20:34","date_gmt":"2019-08-24T18:20:34","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5484"},"modified":"2019-08-24T22:50:40","modified_gmt":"2019-08-25T05:50:40","slug":"leetcode-92-reverse-linked-list-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-92-reverse-linked-list-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 92. Reverse Linked List II"},"content":{"rendered":"\n

Reverse a linked list from position m<\/em> to n<\/em>. Do it in one-pass.<\/p>\n\n\n\n

Note: <\/strong>1 \u2264 m<\/em> \u2264 n<\/em> \u2264 length of list.<\/p>\n\n\n\n

Example:<\/strong><\/p>\n\n\n\n

Input:<\/strong> 1->2->3->4->5->NULL, m<\/em> = 2, n<\/em> = 4\nOutput:<\/strong> 1->4->3->2->5->NULL<\/pre>\n\n\n\n
Solution: <\/strong><\/p>\n\n\n\n
  1. Store the m – 1 and m-th item as prev and tail before reversing<\/li>
  2. Reverse the m to n, return the head and tail->next of the reversed list<\/li>
  3. Reconnect prev and head, tail and tail->next<\/li><\/ol>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  ListNode* reverseBetween(ListNode* head, int m, int n) {\n    ListNode dummy(0);\n    dummy.next = head;\n    ListNode* p = &dummy;\n    \/\/ Find the m-1 th node\n    for (int i = 0; i < m - 1; ++i) \n      p = p->next;\n    ListNode* prev = p;\n    ListNode* curr = p->next;\n    ListNode* tail = curr;    \n    \/\/ Reverse from m to n\n    for (int i = m; i <= n; ++i) {\n      ListNode* next = curr->next;\n      curr->next = prev;\n      prev = curr;\n      curr = next;\n    }    \n    \/\/  Connect three parts\n    p->next = prev;\n    tail->next = curr;\n    return dummy.next;\n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n    dummy = ListNode(0)\n    dummy.next = head\n    p = dummy\n    for i in range(m - 1):\n      p = p.next\n    prev = p\n    curr = p.next\n    tail = curr\n    for i in range(n - m + 1):\n      next = curr.next\n      curr.next = prev\n      prev = curr\n      curr = next\n    p.next = prev\n    tail.next = curr\n    return dummy.next\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Reverse a linked list from position m to n. Do it in one-pass. Note: 1 \u2264 m \u2264 n \u2264 length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output:…<\/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":[83,177,246],"class_list":["post-5484","post","type-post","status-publish","format-standard","hentry","category-list","tag-list","tag-medium","tag-reverse","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5484","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=5484"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5484\/revisions"}],"predecessor-version":[{"id":5489,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5484\/revisions\/5489"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5484"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5484"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}