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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    struct ListNode *slow,*fast;//快慢指针用来定位反转区间
	struct ListNode *pHead = malloc(sizeof(*pHead));//定义一个头节点
	pHead->val = -1;//初始化头节点
	pHead->next = head;//
	
	slow = pHead;//满指针指向头节点
	fast = head;//快指针指向第一个有效节点
				//满指针比快指针在前一个是因为为了保留反转区间第一个节点的前一个节点
	for(int i = 0; i < n-m; i++)//定位反转区间第一步
		fast = fast->next;
	
	for(int i = 0; i < m-1; i++)//定位反转区间第二步
	{
		slow = slow->next;
		fast = fast->next;
	}
	//此时slow指针指向反转区间的前一个结点，fast指针指向反转区间的最后一个节点
	struct ListNode *pre,*cur,*nex,*p,*q;
	p = slow->next;	//保留反转区间的第一个节点，反转后这个节点就是反转区间的尾节点
	q = fast->next;//保留反转区间最后一个节点的下一个节点，反转后反转区间的尾节点的下一个节点就指向这
	pre = NULL;
	cur = slow->next;
	nex = NULL;
	
	for(int i = 0; i < n-m+1; i++)//开始反转
	{
		nex = cur->next;
		cur->next = pre;
		pre = cur;
		cur = nex;
	}
	
	slow->next = fast;//反转区间的第一个节点的前驱节点的下一个节点指向反转区间最后一个节点(这也是为什么一开始定义slow节点要在fast节点前一个，不然反转区间的前驱节点就丢失了)
	p->next = q;//反转后反转区间的尾节点指向反转之前的尾节点的下一个节点
	
	return pHead->next;
}