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. 方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议
3. 方式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. 总结

逆序打印单链表是一种常见的链表操作，通过递归方式可以优雅地实现。