【剑指offer】面试题 6. 从尾到头打印链表

面试题 6. 从尾到头打印链表

题目描述

输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

Java 实现

ListNode Class

class ListNode {

	int val;

	ListNode next = null;

	ListNode(int val) {

		this.val = val;

	}

	@Override

	public String toString() {

		return val + "->" + next;

	}

}

使用递归

import java.util.ArrayList;

public class Solution {

	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

		ArrayList<Integer> res = new ArrayList<>();

		if (listNode == null) {

			return res;

		}

		res.addAll(printListFromTailToHead(listNode.next));

		res.add(listNode.val);

		return res;

	}

}

使用头插法

import java.util.ArrayList;

public class Solution {

	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

		ArrayList<Integer> res = new ArrayList<>();

		ListNode head = new ListNode(-1);

		while (listNode != null) {

			ListNode newHead = listNode.next;

			listNode.next = head.next;

			head.next = listNode;

			listNode = newHead;

		}

		while (head.next != null) {

			res.add(head.next.val);

			head = head.next;

		}

		return res;

	}

}

使用栈

import java.util.ArrayList;

import java.util.Stack;

public class Solution {

	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

		ArrayList<Integer> res = new ArrayList<>();

		Stack<Integer> stack = new Stack<>();

		while (listNode != null) {

			stack.push(listNode.val);

			listNode = listNode.next;

		}

		while (!stack.isEmpty()) {

			res.add(stack.pop());

		}

		return res;

	}

}

巴特西

【剑指offer】面试题 6. 从尾到头打印链表

最新文章

热门文章