92. 反转链表 II

本题思路:

  例子  m = 2, n =5  1 2 3 4 5 6  -》 1 5 4 3 2 6

  1. 反转index m,n将链表分成三部分,samll {1},反转{2,3,4,5},large{6}

  2. 创建空的dummys,small&samll_head , reverse&reverse_head , large&large_head

  3. 通过变量index 将小于m,大于n的nodes放入small large,并保存其首尾,用于最后三个链表拼接

  4. 重点是 中间部分的反转与首位部分的保存

reverse:

  1. A B C / reverse, head, head.next三个节点调换位置 需要第四个临时变量:保存head.next

  2. temp = head.next

      head.next = reverse 

      reverse  = head

      head = temp

  3. 最后reverse链表的头节点是reverse,尾节点不能直接用reverse_head 因为还是空节点,需要往后一位得到尾节点

    if reverse_head.val == None:  reverse_head = head

拼接:

  small.next = reverse

  reverse_head.next = large_head.next

  large.next = None (可以不要)

  return small_head.next

原文地址:https://www.cnblogs.com/ChevisZhang/p/13601199.html