单链表如何实现反转？
实现效果：
null -> e1 -> e2 -> e3
反转后：
null <- e1 <- e2 <- e3
数据结构是单链表，特点是每个节点有一个指针指向后继节点。
我们直接看代码：
package com.itzhimei.base.algorithm;
/**
* @Auther: www.itzhimei.com
* @Description:
* 核心逻辑：
*指针是依次往后挪动的
*首先备份当前节点的next，防止反转过程中，丢失后续节点，造成错误
*/
public class 单链表反转3 {
public static void main(String[] args) {
Element3 e1 = new Element3();
Element3 e2 = new Element3();
Element3 e3 = new Element3();
Element3 e4 = new Element3();
Element3 e5 = new Element3();
e1.name = "e1"; e1.next=e2;
e2.name = "e2"; e2.next=e3;
e3.name = "e3"; e3.next=e4;
e4.name = "e4"; e4.next=e5;
e5.name = "e5";
System.out.println("反转前");
Element3 p1 = e1;
while (p1 != null) {
System.out.println(p1.name);
p1 = p1.next;
}
revert(e1);
System.out.println("反转后");
Element3 p2 = e5;
while (p2 != null) {
System.out.println(p2.name);
p2 = p2.next;
}
}
/**
* prev curr next 反转第三个元素时的状态
* | | |
* prev curr next 反转第二个元素时的状态
* | | |
* prev curr next 反转第一个元素时的状态
* | | |
* null -> e1 -> e2 -> e3
* 反转结果：
* null <- e1 <- e2 <- e3
* @param element3
*/
public static void revert(Element3 element3) {
Element3 curr = element3;
Element3 prev = null;
while(curr != null) {
//指针是依次往后挪动的
//首先备份当前节点的next，防止反转过程中，丢失后续节点，造成错误
Element3 next = curr.next;
//next备份了，马上修改当前节点的next指针
//这里反转了链表next指向的元素
curr.next = prev;
//然后指针向后移动一位，继续后续节点的反转
prev = curr;
curr = next;
}
}
}
class Element3 {
String name;
Element3 next;
}
输出结果：
反转前
e1
e2
e3
e4
e5
反转后
e5
e4
e3
e2
e1遍历反转的核心逻辑是注释上画出来的：
/**
* prev curr next 反转第三个元素时的状态
* | | |
* prev curr next 反转第二个元素时的状态
* | | |
* prev curr next 反转第一个元素时的状态
* | | |
* null -> e1 -> e2 -> e3
* 反转结果：
* null <- e1 <- e2 <- e3
*
*/prev：前一节点
curr：当前节点
next：后继节点
反转的逻辑是：指针是依次往后挪动的，首先备份当前节点的next，防止反转过程中，丢失后续节点，造成错误，Element3 next = curr.next;。next备份了，马上修改当前节点的next指针，这里反转了链表next指向的元素，curr.next = prev；然后指针向后移动一位，继续后续节点的反转
prev = curr;
curr = next;