题解 | #链表内指定区间反转#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
      // 空处理
      if (m == n || head == nullptr) {
        return head;
      }

      // 为链表添加一个头节点
      ListNode myHead(0);
      myHead.next = head;

      // 将指针指向第m个数的前一个
      ListNode* it = &myHead;
      for (int i = 1; i < m; i++) {
        it = it->next;
      }

      // it为改变后的链表
      // it2用于保存需要头插的第一个值 将it与it2断开
      ListNode* it2 = it->next;
      it->next = nullptr;

      // temp指向it2头插后剩下的链表
      ListNode* temp;
      // 共有n + 1 - m个数需要反转
      for (int i = m; i <= n; i++) {
        temp = it2->next;
        it2->next = it->next;
        it->next = it2;
        it2 = temp;
      }

      // 利用it3 访问到it的最后一个非空值
      ListNode* it3;
      for (it3 = it; it3->next != nullptr; it3 = it3->next) {
      }
      // 将temp即剩下未改变的链表插入到it中
      it3->next = temp;
      return myHead.next;
    }
};