链表一种常见的数据结构

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表的反转目前主要包含3种

1.整个链表的反转

2.从链表的头节点开始的前N个节点

3.反转链表的指定M到N的节点   M>=1 

首先开始第一节操作 

1. 整个链表的反正

1.1 方法一 非递归 代码不是很优雅 但不容易造成栈溢出

直接上代码 

讯享网

循环的思路简单列出来 
这里将链表中节点的数字展示出来 方便理解
输入 1->2->3->4->5->6
第一次循环 cur = head = 1 tmp = 2  cur.next = 之前1->2   —–> 1->null  pre = 1  cur = 2
第二次循环 tmp = 3 cur.next = 之前 2->3  —–>  2->1  pre = 2 cur= 3
第三次循环 tmp =4 cur.next = 之前  3->4   —–>  3->2  pre = 3 cur= 4
第四次循环 tmp=5 cur.next = 之前 4->5 —–> 4–> 3  pre = 4 cur = 5
第五次循环 tmp=6  cur.next = 之前 5->6  —–> 5->4  pre = 5 cur= 6
第六次循环 tmp = null  cur.next =  之前 6->null —-> 6->5
返回

1.2 递归方案 方法简单粗暴

讯享网

配置打印的注释帮助理解一波

原有链表 1->2->3->4->5->6
第一次 方法进行调用时 1 revert 参数 ->1
第二次 2. revert 参数 -> 2
第三次 3  revert 参数 -> 3
第四次 4. revert 参数 -> 4
第五次 5.revert 参数 -> 5
第六次 6.revert 参数 ->6 return last  6 方法结束
回到第五次 head = 5   head.next.next= 6.next = 5      5->6  6->5  成环
下一步操作 head.next = null 5.next = null  即此时链表恢复正常 6->5 返回 last = 6
第四次 head = 4  head.next.next= 5.next =4   4->5  5->4  成环
下一步操作 head.next = null 4.next =null 返回  上一步操作 链表为 6->5 经过此次操作 5->4  最后此时链表为 6->5->4 返回 last=6
第三次 head = 3  head.next.next= 3.next =3   3->4  4->3  成环
下一步操作 head.next = null 3.next =null 返回    最后此时链表为 6->5->4->3 返回 last=6
第二次 head = 2  head.next.next= 2.next=2   2->3  3->2  成环
下一步操作 head.next = null 2.next =null 返回    最后此时链表为 6->5->4->3->2 返回 last=6
第一次操作 head =1 head.next.next= 2.next=1 1->2 2->1 成环
下一步操作 head.next = null 1.next = null 返回    最后此时链表为 6->5->4->3->2->1 返回 last=6
至此操作翻转完成
 

讯享网

以上常见两种反转链表操作

2. 反转链表的前N个节点 

 revertN(HEAD,3)  head = 1  n =3
 第二次 head.next =2  n-1=3-1=2
 第三次 head.next =3 n-1 = 2-1 = 1    返回 head =3
 返回第二次 head =2 2.next.next = head —–> 2->3->4->5->6  —> 2->3->2  head.next = 3->2->4->5->6
第二步重点 2->3->2  2.next = 2->4  但是 3还是->2的 也就变成 3->2->4->5->6
 返回第一次 head =1  1.next.next= 1->2->3 —> 1—>2–>1  head.next= = 1-> 4 = 3->2->1->4->5->6
第一步重点 1->2->1  1.next =1->4  但是 2还是->1的 也就变成 3->2->1->4->5->6

3. 反转链表的m - n个节点  其中m>=1  

讯享网

第一次 revertBetween(HEAD,3,5) 实际传入值 head=1 m=3 n=5
第二次调用 head=1 head.next=2 m-1=2  n-1=4 实际传入值 head=2 m=2 n=4
第三次调用 head=2 head.next=3  m-1=1 n-1=3 回到 revertN(3,3)
进入 revertN(3,3)  3->4->5->6  反转前3个 返回 5->4->3->6
回到第二次 head =2 head.next = 2->5->4->3->6
回到第一次 head = 1 head.next = 1->2->5->4->3->6

4. 循环反转 a->b之间的节点

学习文章  递归反转链表：如何拆解复杂问题

讯享网

good day ！！！