剑指Offer第5题---从尾到头打印链表
Peng's Blog 只记录和技术相关的东西

剑指Offer第5题---从尾到头打印链表


题目描述

输入一个链表,从尾到头打印链表每个节点的值。

解题思路

最重要的一点,不能破坏原来链表的结构。
目前我脑子里面能想到两种解法:
1)用栈,栈是先进后出嘛。估计面试官想考的就是这个。
2)递归。高级的递归。

方法1: 栈

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<Integer>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (listNode == null)
			return list;
		while (listNode != null) {
			stack.push(listNode.val);
			listNode = listNode.next;
		}
		while(stack.empty()==false){
			list.add(stack.pop());
		}
		return list;
    }
}

注意:这里有个非常非常重要的点。
注意前面关于链表数据结构的定义,这个在笔试的时候一定一定要自己默写出来啊,不要第一步就死了。
public class ListNode{ int val; ListNode next = null; ListNode(int val){ this.val = val; } } enter description here

方法二 递归

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		if (listNode == null)
			return list;
		if (listNode != null) {
			this.printListFromTailToHead(listNode.next);
			list.add(listNode.val);
		}
		return list;
	}
}

enter description here


Comments

评论功能暂停使用,如需跟作者讨论请联系底部的GitHub