单链表如何实现反转?
实现效果:
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;