92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

复杂度分析

  • 时间复杂度：O(N)，其中 N 是链表总节点数。最坏情况下，需要遍历整个链表。
  • 空间复杂度：O(1)。只使用到常数个变量。

关键点：m的前一个节点；m和n区间的反转；n之后的节点
image.png

  1. //迭代法，和反转链表一致，
  2. //注意翻转后1.先建立原m到n+1的连接；2.断开m-1到m的连接，建立m-1到n连接
  3. func reverseBetween (head *ListNode, m int, n int) *ListNode {
  5.     dummy := &ListNode{}                //申请节点指向头节点
  6.     dummy.Next = head                      //说明第一个是nil空节点a[0]=nil
  7.     prem := dummy
  9.     for i:=1; i < m; i++ {
  10.         prem = prem.Next    //在m-1个数之前（从1开始的实数），prem都是延伸的
  11.     }                       //即m-1的prem  为m-2的prem的下一个，没毛病
  13.     cur := prem.Next    //cur就是第m个点，开始反转
  14.     var pre *ListNode   //定义新链表，从m的前一个开始，与fake保持一致
  16.     for i:=m; i<=n; i++ {   //第n个cur其实变为temp=n+1，执行中间翻转,    有=号啊！
  17.         temp := cur.Next    //先记住n cur的下一个节点
  18.         cur.Next =pre       //翻转链表的节点指向
  19.         pre = cur           //移动链表，依次翻转
  20.         cur =temp           //依次
  21.     }
  23.     prem.Next.Next = cur   //原先m 的下一个：原cur -> 现任cur（n后面一个） 指向n+1，先指向末尾无指向的点1
  24.     prem.Next = pre        //原先指向m的断开，指向n，后断开2建立新连接3
  26.     return dummy.Next       //重新从头再遍历，走一遍指针，链表就建立了
  27. }

方法二：一次遍历「穿针引线」反转链表（头插法）

方法一的缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)O(N)，但遍历了链表 22 次，可不可以只遍历一次呢？
image.png

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就完成了反转。

  • 空间复杂度：O(1)。只使用到常数个变量。

    //头插法
func reverseBetween(head *ListNode, m, n int) *ListNode {
   if head == nil || head.Next == nil {
      return head
   }            

  dummy := &ListNode{Val: 0, Next: head}    //这个定义要记下来，很简洁
  pre := dummy

  for i :=1; i < m; i++ {                 //0 m-1;和1 m是一样的，默认用0开始
      pre = pre.Next
  }

  cur := pre.Next
  for i :=m; i < n; i++ {                    // 注意 不能取=号！ 不然会多翻一位
      temp := cur.Next                    //保存tmp的指向，日后都用它来前进了，链表有下一跳就行
      cur.Next = temp.Next                //1，先找中间的指向
      temp.Next = pre.Next                //2，再找后面的指向，翻转
      pre.Next = temp                        //3，最后找前面的指向，拉为第一个，（左右斜对称！）
  }
  return dummy.Next
}