• 题目
• 题解

题目

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

示例 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

题解

对于链表的问题，一般都是要建一个 dummy node连上原链表的头结点，以此来规范头节点变动和其他节点变动的代码，进行格式统一。

以题目中的例子来说，变换的是 2,3,4 这三个点，我们需要找到第一个开始变换结点的前一个结点，只要让 pre 向后走 m-1 步即可，用 pre 指向它。由于一次只能交换两个结点，所以我们按如下的交换顺序：

1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> 3 -> 2 -> 4 -> 5 -> NULL // 第一次变换将结点 3 放到结点 1 的后面
1 -> 4 -> 3 -> 2 -> 5 -> NULL // 第二次变换将结点 4 放到结点 1 的后面

可以看出来，总共需要 right-left步即可，因为每次变换都是规律的操作，就以第一次变换进行举例。刚开始，pre 指向结点 1，cur 指向结点 2，然后我们建立一个临时的结点 tmp，用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系，这可以当作一个规律记下来。

每一次节点交换分为以下三个步骤：

• 第一步断开结点 2 和结点 3，将结点 2 的 next 连到结点 4 上：

  cur->next = t->next
  

• 第二步将结点 3 连到结点2的前面，即

  t->next = pre->next
  

• 第三步将结点 1 连到结点 3，即

  pre->next = tmp
  

这里跟常见的链表反转最大的区别在于以前prev、cur会向随着链表遍历反转逐渐向后移动，这里的prev、cur其实指向并没有改变。即这里的prev一直是1， cur一直是2， 是cur->next一直在变化。

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 设置头节点，来规范化头节点反转的特殊情况
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
        // left-1是为了找到开始变换节点的前一节点
        for (int i = 0; i < left - 1; i++) 
            pre = pre->next;
        // 本题中pre和cur不会变动！！
        ListNode* cur = pre->next;
        for (int i = left ; i < right; i++) {
            ListNode* tmp = cur->next;
             // 首先断开临时节点和前面节点的关系
            cur->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        return dummy->next;
    }
};