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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
#include <iostream>
class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param head ListNode类
   * @param m int整型
   * @param n int整型
   * @return ListNode类
   */
  pair<ListNode*, ListNode*> reverseHeadTail(ListNode* head, ListNode* tail) {
    ListNode* pre = new ListNode(-1);
    ListNode* cur = head;
    while (cur != tail) {
      ListNode* tmp = cur;
      cur = cur->next;
      tmp->next = pre;
      pre = tmp;
    }
    cur->next = pre;
    return {cur, head};
  }
  ListNode* reverseBetween(ListNode* head, int m, int n) {
    // write code here
    if (head == NULL) {
      return nullptr;
    }
    if (m == n) {
      return head;
    }
    ListNode* old_pre = new ListNode(0);
    old_pre->next = head;
    ListNode* pre = new ListNode(-2);
    ListNode* cur = head;
    pre->next = cur;
    for (int i = 0; i <m-1; i++) {
      pre = cur;
      cur = cur->next;
    }
    //cur为第m个节点。pre为cur节点的前一个节点。
    cout<<"oldhead"<<cur->val<<endl;
    ListNode* node_m = cur; //第m个节点
    ListNode* node_n = cur; 
    for(int i = 0; i<n-m;i++)
    {
      cur = cur->next;
    }
    node_n = cur; //第n个节点
    ListNode* node_n_next = node_n->next; //第n个节点的下一个节点
    cout<<"node_n"<<node_n->val<<endl;
    auto res = reverseHeadTail(node_m, node_n);
    cout<<"res.first"<<res.first->val<<endl;
    cout<<"res.second"<<res.second->val<<endl;
    cout<<pre->val<<endl;
    cout<<"node_m.val"<<node_m->val<<endl;
    pre->next = res.first;
    res.second->next = node_n_next;
    if(res.second == head)
    {
      return res.first;
    }
    return head;
  }

};

我终于做出来了。经过了好长时间的debug, 终于做出来了！！！！

核心思路是：先定位到第m个节点和第n个节点，然后将这一段链表传入进行翻转，再进行接入原来链表。

主要卡壳的地方是：原始链表的头节点如果变成了尾节点，需要做特殊判断，而不是一概返回头节点。

时隔3个月，再次开始刷题，感觉很不错。以后可以通过刷题来娱乐啦！！！不用通过刷题找工作啦！！！！