[链表]剑指Offer06-从尾到头打印链表

[链表]–从尾到头打印链表

题目链接

剑指Offer 06.从尾到头打印链表

题目

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

示例

输入：head = [1,3,2]
输出：[2,3,1]
           

解析

又是反向输出？

用栈！

1压栈；2出栈；3.来一个装一个

嘶…这时间39%玄乎了！再想想！

代码实现

public class Offer06 {

    /**
     * Definition for singly-linked list
     */
    class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 1.将所有结点的值依次压栈
     * 2.弹出所有元素装入数组
     */
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        int[] result = new int[stack.size()];
        int k = 0;
        while (!stack.isEmpty()) {
            result[k++] = stack.pop();
        }
        return result;
    }
}
           

两次遍历：

第一次遍历，求链表长度；

第二次遍历，反下标访问装入数组。

这时间舒服了

代码实现

public class Offer06 {

    /**
     * Definition for singly-linked list
     */
    class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 遍历两趟链表, 第一次统计个数, 第二次装入数组
     */
    public int[] reversePrint(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        int[] result = new int[count];
        cur = head;
        for (int i = count - 1; i >= 0; i--) {
            result[i] = cur.val;
            cur = cur.next;
        }
        return result;
    }
}
           

-----------------------------------------------------------------------------有始有终分割线----------------------------------------------------------------------------------