立志用最少的代碼做最高效的表達

---

輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值（用數組返回）。

示例 1：

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

限制：

0 <= 鏈表長度 <= 10000

---

文章目錄

• 解法1：棧
• 解法2
• 解法3
• 完整可運行代碼
• 測試用例
• 本題考點

---

---

解法1：棧

利用棧先進后出的原理，將鏈表遍歷并存入棧，新建數組，將棧依次彈出，
得到的就是倒序的數組。
本來遍歷一遍就出結果的題，我也不知為啥腦子抽了要用棧。。

class Solution6 {public int[] reversePrint(ListNode head) {// 避免出現空指針if(head == null) return new int[0];List<Integer> array = new ArrayList<Integer>();int num = 0;Stack<Integer> st = new Stack<Integer>();while(true) {st.push(head.val);head = head.next;if(head == null) {break;}}while(!st.empty()) {num++;array.add(st.peek());st.pop();}return array.stream().mapToInt(Integer::valueOf).toArray();} }

---

解法2

直接使用ArrayList動態數組，將棧值依次放入數組，然后遍歷數組，將數組置換，或使用reverse()。最后轉化為int[]即可。

class Solution7 {public int[] reversePrint(ListNode head) {// 避免出現空指針if(head == null) return new int[0];List<Integer> list = new ArrayList<Integer>();while(true) {list.add(head.val);head = head.next;if(head == null) break;}int len = list.size()-1;int num = 0;while(num < len) {int t = list.get(num);list.set(num, list.get(len));list.set(len, t);num++; len--;}return list.stream().mapToInt(Integer::valueOf).toArray();} }

---

解法3

先進行一遍遍歷，將鏈表長度求出，然后定義對應長度的int數組，最后倒序賦值，返回即可。

class Solution8 {public int[] reversePrint(ListNode head) {// 避免出現空指針if(head == null) return new int[0];int count = 0;ListNode tmp_head = head;while(tmp_head != null) {count++;tmp_head = tmp_head.next;}int array[] = new int[count];for(int i = count-1; i >= 0; i--) {array[i] = head.val;head = head.next;}return array;} }

完整可運行代碼

import java.util.ArrayList; import java.util.List; import java.util.Stack; import java.util.Vector;public class 劍指_Offer_06_從尾到頭打印鏈表 {public static void main(String[] args) {// 聲明鏈表，這里的Solution6、7、8分別代表三種解法。Solution8 solution = new Solution8();ListNode head = new ListNode(1);ListNode n1 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);n4.next = n5;n3.next = n4;n1.next = n3;head.next = n1;// 輸出數組int node[] = solution.reversePrint(head);for(int i = 0; i < node.length; i++) {System.out.println(node[i] + " ");}} }class ListNode {int val;ListNode next;ListNode(int x) { val = x; } }// 解法1：棧 // 利用棧先進后出的原理，將鏈表遍歷并存入棧，新建數組，將棧依次彈出， // 得到的就是倒序的數組。 // 本來遍歷一遍就出結果的題，我也不知為啥腦子抽了要用棧。。 class Solution6 {public int[] reversePrint(ListNode head) {// 避免出現空指針if(head == null) return new int[0];List<Integer> array = new ArrayList<Integer>();int num = 0;Stack<Integer> st = new Stack<Integer>();while(true) {st.push(head.val);head = head.next;if(head == null) {break;}}while(!st.empty()) {num++;array.add(st.peek());st.pop();}return array.stream().mapToInt(Integer::valueOf).toArray();} }// 解法2，直接使用ArrayList動態數組，最后轉化為int即可。 class Solution7 {public int[] reversePrint(ListNode head) {// 避免出現空指針if(head == null) return new int[0];List<Integer> list = new ArrayList<Integer>();while(true) {list.add(head.val);head = head.next;if(head == null) break;}int len = list.size()-1;int num = 0;while(num < len) {int t = list.get(num);list.set(num, list.get(len));list.set(len, t);num++; len--;}return list.stream().mapToInt(Integer::valueOf).toArray();} }// 解法3，先進行一遍遍歷，將鏈表長度求出，然后定義對應長度的int數組，最后倒序賦值，返回即可。 class Solution8 {public int[] reversePrint(ListNode head) {// 避免出現空指針if(head == null) return new int[0];int count = 0;ListNode tmp_head = head;while(tmp_head != null) {count++;tmp_head = tmp_head.next;}int array[] = new int[count];for(int i = count-1; i >= 0; i--) {array[i] = head.val;head = head.next;}return array;} }

---

測試用例

• 功能測試：輸入的鏈表有多個節點；輸入的鏈表只有一個節點
• 特殊輸入測試：輸入的鏈表頭結點指針為null

本題考點

• 考查應聘者對單向鏈表的理解和編程能力
• 考查應聘者對循環、遞歸和棧3個相互關聯的概念的理解。

總結

以上是生活随笔為你收集整理的【三种解法】剑指 Offer 06. 从尾到头打印链表【附完整可运行代码】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。