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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        if(!head || m==n) //无需反转，直接返回。
            return head;
        int count=1;  //指针向后移动时自增，标识当前是第几个结点。
        ListNode* loop=head;  //loop:遍历链表结点的指针。
	  
	   //first_end:指向翻转区域前一个结点，为了第一部分和翻转部分拼接。
	  //   mid_end:指向翻转区域翻转前的第一个结点，也是翻转后的最后一个结点，为了翻转部分和后面部分拼接。
        ListNode* first_end, *mid_end, *tmp;
        struct ListNode mid_head ={0}; 
       if(m!=1){
		 	//while循环结束后loop指向翻转区域前一个结点
            while(count!=m-1){
                loop=loop->next;
                count++;
            }
            first_end=loop;  //保存翻转区域前一个结点的位置，也是第一部分最后一个结点
            loop=loop->next; //loop指向翻转区域第一个结点
            mid_end = loop;  //保存翻转区域最后一个结点的位置
            count++;
       }
	  //使用头插法将翻转区域的结点依次插入一个子链表中，退出while循环时，tmp指向了翻转区域后（第三部分）的第一个结点
        while(count<=n){
            tmp = loop->next;
            loop->next = mid_head.next;
            mid_head.next = loop;
            loop=tmp;
            count++;
        }
	  //拼接输出：第一部分未翻转 -> 翻转后子链 -> 第三部分未翻转
        if(m==1){
            head->next = tmp;
            head = mid_head.next;
            return head;
        }
        first_end->next = mid_head.next;
        mid_end->next = tmp;
        return head;

    }
};

问题分析

题目要求元素翻转，想到头插法；又要求特定区间元素，因此考虑使用while循环移动指针，找到目标区间的第一个元素。

具体思路（结合代码）

当给定链表为空，以及m=n时，无需操作，函数输出即是输入。

m<=n时，有两种不同情况：

m=1，从链表第1个元素开始翻转，这样输入链表的第1个元素是返回链表的第n个元素，第n个元素是返回链表的第1个元素；

m>1，输入链表的前m-1个元素保持不变，这时需要一个指针（frst_end）指向第m-1个元素，方便其指向翻转区域链表的第1个元素，使第1部分未翻转的子链 和 第2段已翻转子链 连接起来。

以上并没考虑翻转区域是否涵盖到链表的最后一个元素，因为无论后面是空指针NULL还是链表结点，只要让翻转后链表最后一个元素指向遍历结束后的tmp就行了。

复杂度分析

时间复杂度：最坏情况下对所有元素进行翻转，时间复杂度和链表元素长度为线性关系，为O(n)。

空间复杂度：只创建了一个ListNode结点作为尾插链表的非值头结点，为O(1)。