📑 题目：92. 反转链表 II

🚀 本题 LeetCode 传送门

题目大意

给定 2 个链表中结点的位置 m, n，反转这个两个位置区间内的所有结点。

解题思路

由于有可能整个链表都被反转，所以构造一个新的头结点指向当前的头。之后的处理方法是：找到第一个需要反转的结点的前一个结点 p，从这个结点开始，依次把后面的结点用“头插”法，插入到 p 结点的后面。循环次数用 n-m 来控制。

这一题结点可以原地变化，更改各个结点的 next 指针就可以。不需要游标 p 指针。因为每次逆序以后，原有结点的相对位置就发生了变化，相当于游标指针已经移动了，所以不需要再有游标 p = p.Next 的操作了。

代码

  1. package leetcode
  3. /**
  4.  * Definition for singly-linked list.
  5.  * type ListNode struct {
  6.  *     Val int
  7.  *     Next *ListNode
  8.  * }
  9.  */
  11. func reverseBetween(head *ListNode, m int, n int) *ListNode {
  12.  if head == nil || m >= n {
  13.   return head
  14.  }
  15.  newHead := &ListNode{Val: 0, Next: head}
  16.  pre := newHead
  17.  for count := 0; pre.Next != nil && count < m-1; count++ {
  18.   pre = pre.Next
  19.  }
  20.  if pre.Next == nil {
  21.   return head
  22.  }
  23.  cur := pre.Next
  24.  for i := 0; i < n-m; i++ {
  25.   tmp := pre.Next
  26.   pre.Next = cur.Next
  27.   cur.Next = cur.Next.Next
  28.   pre.Next.Next = tmp
  29.  }
  30.  return newHead.Next
  31. }