题目链接

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例

示例1：

输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]

提示

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500

  • 1 <= left <= right <= n

    思路

    思路1：迭代（头插法）

    以示例一为例：
    0092-反转链表II - 图1
    0092-反转链表II - 图2

    思路2：递归

    与0206-反转链表类似。

    题解

    思路1：迭代（头插法）

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12.  public:
    13.   ListNode* reverseBetween(ListNode* head, int left, int right) {
    14.       ListNode dummyHead = ListNode(0);
    15.       dummyHead.next = head;
    16.       ListNode* prev = &dummyHead;
    17.       for (int i = 0; i < left - 1; ++i) {
    18.           prev = prev->next;
    19.       }
    20.       ListNode* curr = prev->next;
    21.       ListNode* next;
    22.       for (int i = 0; i < right - left; ++i) {
    23.           next = curr->next;
    24.           curr->next = next->next;
    25.           next->next = prev->next;
    26.           prev->next = next;
    27.       }
    29.       return dummyHead.next;
    30.   }
    31. };

    思路2：递归

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12.  private:
    13.   ListNode* processReverse(ListNode* head, int n) {
    14.       if (n == 0 || head == nullptr || head->next == nullptr) {
    15.           return head;
    16.       }
    17.       ListNode* p = processReverse(head->next, n - 1);
    18.       ListNode* temp = head->next->next;
    19.       head->next->next = head;
    20.       head->next = temp;
    21.       return p;
    22.   }
    24.  public:
    25.   ListNode* reverseBetween(ListNode* head, int left, int right) {
    26.       ListNode dummyHead = ListNode(0);
    27.       dummyHead.next = head;
    28.       ListNode* prev = &dummyHead;
    29.       for (int i = 0; i < left - 1; ++i) {
    30.           prev = prev->next;
    31.       }
    32.       prev->next = processReverse(prev->next, right - left);
    34.       return dummyHead.next;
    35.   }
    36. };

    复杂度分析

    思路1：迭代（头插法）

  • 时间复杂度：0092-反转链表II - 图3

  • 空间复杂度：0092-反转链表II - 图4

    思路2：递归

  • 时间复杂度：0092-反转链表II - 图5

  • 空间复杂度：0092-反转链表II - 图6