一、简介

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。

给出的链表为 1 => 2 => 3 =>4 => 5 => NULL，m=2,n=4

返回 返回 1→4→3→2→5→NULL

二、实现

思路：找到待翻转的起点，从起点开始翻转即可，需要注意起点可能是头指针。

func reverseBetween( head *ListNode ,  m int ,  n int ) *ListNode {
   // write code here
   if head == nil {
      return nil
   }

   // 不需要翻转
   if m == n {
      return head
   }

   // 起点为头指针
   if m == 1 {
      return reverseStart(head, n - m)
   }

   var (
      parentNode  = head
      startNode = head
   )

   i := 1
   for m > i && startNode != nil{
      parentNode = startNode
      startNode = startNode.Next
      i++
   }

   parentNode.Next = reverseStart(startNode, n - m)

   return head
}

// 从头节点开始翻转n个节点
func reverseStart(p *ListNode,  n int) *ListNode{
   var (
      newHead *ListNode
      nextNode *ListNode
   )

   oldHead := p
   for p != nil && n >= 0 {
      nextNode = p.Next

      p.Next = newHead

      newHead = p
      p = nextNode

      n --
   }

   oldHead.Next = nextNode

   return newHead
}