01-链表原地翻转

题目

1. 翻转一个链表。
   给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null
   要求原地翻转。
2. 翻转链表中第m个节点到第n个节点的部分。m，n满足1 ≤ m ≤ n ≤ 链表长度。
   要求在原地一次翻转完成

链表知识回顾

1. 链表定义

• n个节点离散分布
• 彼此通过指针相连
• 每个节点只有一个前驱节点，每个节点只有一个后续节点
• 首节点没有前驱节点，尾节点没有后续节点

2. 相关术语

• 首节点：第一个有效节点
• 尾节点: 最后一个有效节点
• 头结点：头结点的数据类型和其余结点一样；第一个有效节点之前的那个节点；头节点并不存放有效数据；加头结点的目的是为了方便对链表的操作（待体会）
• 头指针： 指向头结点的指针变量
• 尾指针： 指向尾节点的指针变量
  确定一个链表只需要一个参数：头指针即可

3. 链表分类

• 单链表
• 双链表 每个节点有两个指针域
• 循环链表 能通过任何一个节点找到找到其他任何节点
• 非循环链表
• 带环的链表

解题思路

1. 题目1：原地一次翻转完成，意味着不能开辟额外的空间，意味着只能改变每个节点next指针的指向，即把每个节点的next指针指向其前一个节点。
   在改变节点next指针前，需先保留下next指针的值，保证在改变其next指针后仍旧可以找到其原始next值。

2. 题目2

• 指定翻转的范围按照原地翻转链表的代码就行
• 需要记录开始翻转前的节点，开始翻转的第一个节点，及最后一个节点，用于最后链表的组装。比如1，2，3，4，5，翻转2到4，则需要记录1,2,4。在翻转完成之后，需要将1(prev)指向4(last），2(first)指向5。

参考代码

参考代码使用C++书写，来自九章算法，并且此链表中没有头结点，即链表的第一个节点就是有效节点

1. 题目1

   
   Snip20190105_20.png

2. 题目2

   
   Snip20190105_21.png