剑指offer06:从尾到头打印链表

2021年11月25日 阅读数:3
这篇文章主要向大家介绍剑指offer06:从尾到头打印链表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目描述:html

输入一个链表的头节点,从尾到头反过来返回每一个节点的值(用数组返回)。java

示例 1:数组

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

解题思路:ide

从尾到头打印链表,优先考虑栈,由于想到栈是先进后出的。若是先反转链表再打印的话会破坏链表原来的结构,不建议。指针

  • 建立一个栈,用于存储链表的节点Stack<ListNode>;
  • 建立一个指针,初始时指向链表的头节点。

当指针指向的元素非空时,重复下列操做:code

  • 将指针指向的节点压入栈内
  • 将指针移到当前节点的下一个节点

得到栈的大小 size,建立一个数组 print,其大小为 sizehtm

  • 建立下标并初始化 index = 0
  • 重复 size 次下列操做:
  • 从栈内弹出一个节点,将该节点的值存到 print[index]
  • 将 index 的值加 1
  • 返回 print

 

java代码:it

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
         
        
                 
        Stack<ListNode> stack=new Stack<>();
        ListNode cur=head;
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        int size=stack.size();
        int[] array=new int[size];
        for(int i=0;i<size;i++){
            array[i]=stack.pop().val;
            
        }
        return array;
    }
}