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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */

 //查找
struct ListNode* SLFind(struct ListNode* phead, int x)
{
     int count=0;
	//循环遍历查找
	struct ListNode* cur = phead;
	while(cur)
	{
        count++;
        if(count==x) return cur;
		cur = cur->next;
	}
    return NULL;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) 
{
    // write code here
    //若m的值大于n的情况（给反了)则不进行反转
    if(m>n) return head;
    //找到m之后将m-n之间的节点插入到n后面
    //查找到m和n位置节点
    struct ListNode* cm=SLFind(head,m);
    struct ListNode* cn=SLFind(head,n);
    //仅有一个节点的情况 或者cm和cn是同一个节点的情况
    //cm 或者 cn不存在的情况
    if(head->next==NULL || cm==cn || cm==NULL || cn==NULL)
    {
        return head;
    }
    
    //至少存在两个节点，且cn和cm都存在，且cm和cn并非是同一个节点
    //① cm为头，cn为尾的情况
    if(cm==head)
    {
       //cn为尾或者不为尾的情况
        while(cm!=cn)
        {
            struct ListNode* n_next=cn->next;
            struct ListNode* m_next=cm->next;
            cn->next=cm;
            cm->next=n_next;
            n_next=cm;
            cm=m_next;
        }
        head=cn;
        return head;
    }
   
   //cm不为头，cn为尾或不为尾的情况,此情况下至少存在3个节点
   //寻找cm的前一个节点
   struct ListNode* pevr=head;
   struct ListNode* cur=head;
   while(cur!=cm)
   {
      pevr=cur;
      cur=cur->next;
   }

   while(cm!=cn)
   {
      struct ListNode* n_next=cn->next;
      struct ListNode* m_next=cm->next;
      cn->next=cm;
      cm->next=n_next;
      pevr->next=m_next;
      cm=m_next;
   }
   return head;
}