题意概述

• 对于给定的链表，以及一个给定的区间[m,n]
• 将该子区间的链表结点反转

方法一：反转next指针

思路与具体做法

• 首先将链表在第m，n个数旁断开链表，形成三个子链表
• 对中间的需要反转的子链表反转后
  • p指针：指向反转区域内的当前结点
  • next指针：指向p的后继
  • pre指针：指向p的前驱
  • 依次令p指针的next指针反转，然后后移next指针遍历完所有待反转链表即可
• 再和左右两个子链表拼接成一个链表即可

	class Solution {
	public:
		void reverse(ListNode* head){
			ListNode* p=head,*pre=NULL,*next=p->next;
			while(p){
				p->next=pre;//反转next指针
				pre=p;
				p=next;
				next=p->next; 
			}
		}
	    ListNode* reverseBetween(ListNode* head, int m, int n) {
	    	ListNode* head2=new ListNode(0); 
	    	head2->next=head;
			ListNode *p1=head2,*p2,*p3=head2,*p4;
			for(int i=0;i<n;i++){//p1指向第m-1个结点,p3指向第n个结点 
				if(i<m-1)p1=p1->next;
				p3=p3->next;
			}
			p2=p1->next;//p3指向第m个结点 
			p4=p3->next;//p4指向第n+1个结点 
			p1->next=NULL;//截取子链表 
			p3->next=NULL; 
			reverse(p2);//反转子链表
			p1->next=p3;//合并回原先的链表 
			p2->next=p4; 
			return head2->next; 
	    }
	};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历了一次链表
• 空间复杂度：$O\left(1\right)O(1)$O(1)， 仅新建了一个伪头结点和几个指针

方法二：头插法

思路与具体做法

• 对需要反转的区域使用头插法，每遍历到一个结点，就将该结点头插到要反转的区域前
  • p指针：指向反转区域内的当前结点
  • next指针：指向p的后继
  • pre指针：指向p的前驱
• 头插法操作步骤
  • 当前结点指向后继的后继：p->next=next->next;
  • 后继结点指向当前结点：next->next=pre->next;
  • 前驱结点指向后继结点：pre->next=next;
  • 之后令next后移，遍历完所有要反转结点

	class Solution {
	public:
	    ListNode* reverseBetween(ListNode* head, int m, int n) {
	    	ListNode* head2=new ListNode(0); //新建一个假的头结点，方便找第m个结点的前驱 
	    	head2->next=head;
	    	ListNode *pre=head2;
	    	for(int i=0;i<m-1;i++){//pre指向第m-1个结点 
	    		pre=pre->next;
			}
			ListNode *p=pre->next;//p指向第m个结点 
			ListNode *next=p->next;
			for(int i=0;i<n-m;i++){//要n-m要反转结点依次进行反转，具体为对next指向结点头插法插入p指向结点前 	 
				p->next=next->next;//当前结点指向后继的后继 
				next->next=pre->next;//后继结点指向当前结点 
				pre->next=next;//前驱结点指向后继结点 
				next=p->next;//后移后继结点
			}
			return head2->next;
	    }
	};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历了一次链表
• 空间复杂度：$O\left(1\right)O(1)$O(1)， 仅新建了一个伪头结点和几个指针