题解 | 思路最清晰、最易懂的链表内指定区间反转

/**
 * 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) {
        // 遇到m==n或者空头节点的情况，直接返回head
        if(m==n || head == nullptr) return head;
        // 创建假节点fake指向head，避免遇到m=1时，我们没法找到m-1的节点。让假节点指向head。使用fake_node，相当于让m至少为2，简化了问题
        ListNode* fake_node = new ListNode(-1);
        fake_node->next = head;
        // 以fake为起点，右移m-1次，找到第m-1个节点，叫做prev_m
        ListNode* prev_m = fake_node;
        for(int i=1; i<m; ++i)
        {
            prev_m = prev_m->next;
        }
        // 通过prev_m找到第m个起点，叫做node_m
        ListNode* node_m = prev_m->next; 
        // 以node_m为起点，右移n-m次，找到第n个节点，叫做node_n。第n+1个节点，叫做after_n
        ListNode* node_n = node_m;        
        for(int i = m; i<n; ++i)
        {
            node_n = node_n->next;
        }
        ListNode* after_n = node_n->next;
        // 对m与n之间的节点进行反转。与普通的反转链表不同过得是，while结束条件从cur!=nullprt改成cur!=after_n
        ListNode* pre = nullptr;
        ListNode* cur = node_m;
        ListNode* tmp = nullptr;
        // 进行普通的反转链表      反转前 pre->cur->tmp->...，反转后 pre<-cur 断开 tmp->... 
        while(cur != after_n)
        {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        // 让第m-1节点连接第n个节点
        prev_m->next = node_n;
        // 让第m节点连接第n+1个节点
        node_m->next = after_n;
        // 返回假表头的邻居
        ListNode* real_head = fake_node->next;
        delete fake_node;
        return real_head;
    }
};

核心思想

使用pre_m、node_m、node_n、after_n记录左断点、右断点。 然后对node_m与node_n进行普通的反转链表。结束后，让pre_m右接node_n，让node_m右接after_n

边界情况

1. 遇到m==n或者SIZE=1时，直接返回head
2. 对于m=1的情况，为了能够找到m-1节点。 我们在head之前插入一个fake节点。 最终返回fake->next作为我们的结果链表