题目链接

LeetCode

题目描述

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

示例 1：

92. 反转链表 II* - 图1

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

示例 2：

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

提示：

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

进阶： 你可以使用一趟扫描完成反转吗？

解题思路

方法一：双指针

记录左链表和右链表，反转中间的链表，然后链接左右链表
我们还需要记录left的前一个节点，和right的后一个节点。如图所示：
92. 反转链表 II* - 图2
92. 反转链表 II* - 图3

  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.         if(head==nullptr||left>=right)
  15.             return head;
  17.         ListNode* hair = new ListNode();
  18.         hair->next = head;
  19.         // 记录head前的结点
  20.         ListNode* prev = hair;
  21.         // 记录当前位置
  22.         int pos = 1;
  23.         // 找到开始反转位置
  24.         // 反转位置开始结点为head
  25.         while(pos<left&&head!=nullptr){
  26.             prev = head;
  27.             head = head->next;
  28.             ++pos;
  29.         }
  30.         // 如果第一个反转结点为空，则不需要反转
  31.         if(head==nullptr)
  32.             return hair->next;
  33.         // 记录开始反转结点左边的第一个结点
  34.         ListNode* pleft = prev;
  35.         // 记录第一个反转结点,第一个反转结点为反转链表的尾结点
  37.         ListNode* pright = head;
  38.         // 以此反转结点，直至反转完成或者到达链表结尾
  39.         while(pos<=right&&head!=nullptr){
  40.             pos++;
  41.             ListNode* tmp = head->next;
  42.             head->next = prev;
  43.             prev = head;
  44.             head = tmp;
  45.         }
  46.         // 将左边链表链接上反转最后一个结点
  47.         pleft->next = prev;
  48.         // 将反转后的结点链接到右边链表
  49.         // head为右边链表的头结点
  50.         pright->next = head;
  51.         // 返回头结点
  52.         return hair->next;
  53.     }
  54. };
  • 时间复杂度 O(n)

  • 空间复杂度 O(1)

    方法二：反转链表（头插法）

    在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。
    92. 反转链表 II* - 图4

    class Solution {
public:
  ListNode *reverseBetween(ListNode *head, int left, int right) {
      // 设置 dummyNode 是这一类问题的一般做法
      ListNode *dummyNode = new ListNode(-1);
      dummyNode->next = head;
      ListNode *pre = dummyNode;
      for (int i = 0; i < left - 1; i++) {
          pre = pre->next;
      }
      ListNode *cur = pre->next;
      ListNode *next;
      for (int i = 0; i < right - left; i++) {
          next = cur->next;
          cur->next = next->next;
          next->next = pre->next;
          pre->next = next;
      }
      return dummyNode->next;
  }
};

  • 时间复杂度 O(n)

  • 空间复杂度 O(1)