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

package main  
  
import . "nc_tools"  
  
func reverseBetween(head *ListNode, m int, n int) *ListNode {  
    if head == nil || head.Next == nil || m >= n {  
        return head  
    }  
  
    final := &ListNode{-1, head} // 哑节点  
    start := final               // 开始翻转的节点的前一个节点  
  
    // 找开始翻转的节点的前一个节点  
    for i := 0; i < m-1; i++ {  
        if start.Next == nil {  
            return head // 如果 m 大于链表长度，直接返回原链表  
        }  
        start = start.Next  
    }  
  
    end := start.Next // 开始翻转的节点  
    // 找结束节点（即反转后链表的最后一个节点的下一个节点）  
    for i := 0; i < n-m; i++ {  
        if end == nil {  
            return head // 如果 n 大于链表长度，直接返回原链表  
        }  
        end = end.Next  
    }  
  
    // 保存要反转的节点头部节点  
    leftNode := start.Next  
    // 断开 start 和 end 后的链表  
    nextNode := end.Next  
    start.Next = nil  
    end.Next = nil  
  
    // 开始翻转  
    pre := &ListNode{}  
    cur := leftNode  
    for cur != nil {  
        temp := cur.Next  
        cur.Next = pre  
        pre = cur  
        cur = temp  
    }  
  
    // 接起来  
    start.Next = pre // pre 现在是翻转后子链表的头部节点  
    leftNode.Next = nextNode // 翻转前子链表的最后一个节点连接到翻转后的子链表之后的节点  
  
    return final.Next // 返回新链表的头节点  
}  
  
// ... 其他代码 ...