【剑指offer】从尾到头打印链表

• 👑专栏内容：力扣刷题
• ?个人主页：子夜的星的主页
• 💕座右铭：前路未远，步履不停

---

---

一、题目描述

1、题目

题目链接：剑指offer：从尾到头打印链表

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图：

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

2、示例

示例1

输入：{1,2,3}
返回值：[3,2,1]

示例2

输入：{67,0,24,58}
返回值：[58,24,0,67]

二、题目分析

1、新建数组

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = listNode;
        while(cur!=null){
            list.add(0,cur.val);
            cur = cur.next;
        }
        return list;
    }
}

使用ArrayList来存储链表元素，并通过在ArrayList的开头插入节点值的方式，从而实现将链表元素从尾到头打印的效果。

2、头插法

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode head=new ListNode(-1) ;
        while(listNode!= null){
               ListNode temp=listNode.next; 
               listNode.next=head.next;
               head.next=listNode;
               listNode=temp;
        }
        ArrayList <Integer> res = new ArrayList<Integer>();
        head=head.next; 
        while(head!=null){ 
            res.add(head.val);
            head=head.next;
        }
        return res;
    }
}

3、递归

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (listNode != null) {
            printListFromTailToHead(listNode.next);
            res.add(listNode.val);
        }
        return res;
    }
}

1. ArrayList<Integer> res = new ArrayList<Integer>();创建一个ArrayList对象，用于存储链表元素。

2. if (listNode != null) 进行条件判断，如果当前节点不为null，执行下面的递归和添加操作。这是递归的终止条件。

3. printListFromTailToHead(listNode.next);递归调用自身，传入当前节点的下一个节点。这样就实现了从链表的尾部到头部的递归访问。

4. res.add(listNode.val);将当前节点的值添加到ArrayList中。这是在递归的回溯阶段执行的，确保元素的顺序是从尾到头的。

5. return res;：返回存储了链表元素的ArrayList，其中元素的顺序是从尾到头的。

整个递归的过程是不断地递归访问链表的下一个节点，然后在回溯的过程中将节点的值添加到ArrayList中，最终形成了从尾到头的顺序。递归的终止条件是当前节点为null，即到达链表的尾部。这种递归实现方式是一种比较简洁的方法，但需要注意可能会在处理较长链表时导致栈溢出。