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

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
*/

// 大致思路见注释

func reverseBetween( head *ListNode ,  m int ,  n int ) *ListNode {
    // write code here\
    var pTempHead, pTempTail *ListNode
    pTempHead = head
    pTempTail = head
    
    var pHeadPre *ListNode
    pHeadPre = nil
    
    for m > 1 {    // 找到待翻转部分的起始点
        pHeadPre = pTempTail    // 锁定起始点的前一节点位置，用于后续拼接工作
        pTempTail = pTempTail.Next
        m--
    }
    for n > 1 {    // 找到待翻转部分的终点
        pTempHead = pTempHead.Next
        n--
    }
    
    var pTailNext *ListNode
    pTailNext = pTempHead.Next    // 锁定终点的后一节点位置，用于后续拼接工作
    
    var pWork *ListNode
    pWork = pTempTail
    
    var pPre *ListNode = nil
    var pCurrent *ListNode
    
    for pWork != pTailNext {    // 具体翻转逻辑，即头插法
        pCurrent = pWork
        pWork = pWork.Next
        pCurrent.Next = pPre
        pPre = pCurrent
    }   
 
    // 此处开始皆为拼接工作
    if pHeadPre == nil && pTailNext == nil {    // 如果起始点为原链表的第一个节点，终点为原链表的终点，则进行全翻转
        return pTempHead
    }
    
    if pHeadPre == nil {    // 如果起始点为原链表第一个节点，终点为中间某节点，则只需要拼接翻转后的表的表尾节点和原链表中的n+1号节点
        pTempTail.Next = pTailNext
        return pTempHead
    } else if pTailNext == nil {    // 如果起始点为原链表中某个节点（非第一个），终点为原链表的终点，则只需要拼接原链表的m-1号节点和翻转后的表的表头节点
        pHeadPre.Next = pTempHead
        return head
    } else {    // 如果从中间某段开始反转，则头尾都要拼接
        pHeadPre.Next = pTempHead
        pTempTail.Next = pTailNext
        return head
    }
}