03.2 从尾到头打印单链表
逆序打印单链表：从尾到头的输出之美
1. 逆序打印单链表的基本原理
逆序打印单链表即是将链表的内容从尾到头输出。
2. Python逆序打印单链表的实现方式
2.1 递归法
递归法是一种比较巧妙的方式，通过递归地访问链表的下一个节点，再进行打印，从而达到逆序输出的效果。
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def reverse_print_linked_list(head):
if head is None:
return
reverse_print_linked_list(head.next)
print(head.value, end=" -> ")
2.2利用栈
通过使用栈这一数据结构，将链表的节点值先依次入栈，然后再逐个出栈输出，实现逆序打印的效果。
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def reverse_print_with_stack(head):
stack = []
current = head
while current:
stack.append(current.value)
current = current.next
while stack:
print(stack.pop(), end=" -> ")
print("None")
3. Java逆序打印单链表的实现方式
实现思路：
- 上面的题的要求就是逆序打印单链表.
- 方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议
- 方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
package org.example;
import java.util.Stack;
import static org.example.SinglelinkedList.*;
public class SingleLinkedListDemo {
public static void main(String[] args) {
HeroNode heroNode1 = new HeroNode(1, "一号", "1号");
HeroNode heroNode2 = new HeroNode(2, "二号", "2号");
HeroNode heroNode3 = new HeroNode(3, "三号", "3号");
HeroNode heroNode4 = new HeroNode(4, "四号", "4号");
HeroNode heroNode5 = new HeroNode(4, "五号", "5号");
HeroNode heroNode6 = new HeroNode(6, "六号", "6号");
// 创建链表
SinglelinkedList singlelinkedList = new SinglelinkedList();
// 加入
singlelinkedList.add(heroNode1);
singlelinkedList.add(heroNode2);
singlelinkedList.add(heroNode3);
singlelinkedList.add(heroNode4);
singlelinkedList.list();
singlelinkedList.del(heroNode3);
singlelinkedList.list();
System.out.println("有效的节点个数：" + getLength(singlelinkedList.getHead()));
singlelinkedList.addByOrder(heroNode5);
singlelinkedList.addByOrder(heroNode6);
singlelinkedList.addByOrder(heroNode3);
singlelinkedList.list();
// HeroNode res = findLastIndexNode(singlelinkedList.getHead(), 2);
// System.out.println(res);
System.out.println("反转单链表-------");
reverseList(singlelinkedList.getHead());
singlelinkedList.list();
//未改变链表本身结构
reversePrint(singlelinkedList.getHead());
}
}
//定义SingleLinkedList来管理角色
class SinglelinkedList {
//返回头节点
public HeroNode getHead() {
return head;
}
// 初始化头节点，不动头节点
private HeroNode head = new HeroNode(0, "", "");
public void add(HeroNode heroNode) {
// 添加节点搭配单向链表
// 思路：不考虑编号顺序时，
// 找到当前链表的最后节点，并将其next指向新的节点
HeroNode temp = head;
// 遍历链表，找到最后一个
while (true) {//退出循环时，temp指向最后
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = heroNode;
}
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
// temp位于添加的前一个节点
boolean flag = false;//添加的编号是否存在
while (true) {
if (temp.next == null) {//处在链表最后
break;
}
if (temp.next.no > heroNode.no) {//位置找到了
break;
} else if (temp.next.no == heroNode.no) {
flag = true;//说明编号存在
break;
}
temp = temp.next;
}
// 判断flag
if (flag) {
System.out.println("准备插入的编号已经存在,不能加入");
} else {
//添加到链表中
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 根据no修改节点的信息
public void update(HeroNode heroNode) {
// 判断是否为空
if (heroNode.next == null) {
System.out.println("链表为空");
return;
}
//找到需要修改的节点,根据no修改.遍历
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.nickname = heroNode.nickname;
temp.name = heroNode.name;
} else {
System.out.println("未找到编号");
}
}
public void del(HeroNode heroNode) {
// 判断是否为空
if (heroNode.next == null) {
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println("要删除的不存在");
}
}
/**
* @param head 链表头节点
* @return 返回有效节点的个数
*/
//获取单链表有效节点的个数（带头节点需要不统计头节点）
public static int getLength(HeroNode head) {
if (head.next == null) {
return 0;
}
int length = 0;
// 定义辅助节点，不统计头节点
HeroNode cur = head.next;
while (cur != null) {
length++;
cur = cur.next;
}
return length;
}
//查找单链表的倒数第k个节点\
// 1.编写方法接受head节点，同时接收index表示倒数第index个节点
// 2.先把链表从头到尾遍历，length-index
public static HeroNode findLastIndexNode(HeroNode head, int index) {
if (head.next == null) {
return null;
}
// 第一次遍历，得到链表长度
int length = getLength(head);
// 第二次遍历length-index
if (index <= 0 || index > length) {
return null;
}
HeroNode temp = head.next;
for (int i = 0; i < length - index; i++) {
temp = temp.next;
}
return temp;
}
public static void reverseList(HeroNode head) {
if (head.next == null || head.next.next == null) {
return;
}
HeroNode cur = head.next;
HeroNode next = null;
HeroNode reverseHead = new HeroNode(0, "", "");
// 遍历原来的链表
while (cur != null) {
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
head.next = reverseHead.next;
}
public static void reversePrint(HeroNode head) {
if (head.next == null) {
return;
}
// 创建栈，将各个节点压入栈
Stack<HeroNode> stack = new Stack<>();
HeroNode cur = head.next;
// 将链表所有节点压入栈中
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
//打印栈中节点
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
// 显示链表
public void list() {
// 先判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 因为头节点不能动，因此需要辅助变量进行遍历
HeroNode temp = head.next;
while (true) {
if (temp == null) {
return;
}
// 输出节点信息|
System.out.println(temp);
// temp后移
temp = temp.next;
}
}
}
//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;
// 构造器
public HeroNode(int no, String name, String nickname) {
this.name = name;
this.no = no;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
4. 总结
逆序打印单链表是一种常见的链表操作，通过递归方式可以优雅地实现。