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

难度: 简单

来源: 剑指 OFFER

---

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

 

示例 1：

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

限制：

0 <= 链表长度 <= 10000

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {

    }
}

分析与题解

---

• API利用法

  需要把链表从尾部到头部依次返回, 我们就首先全部添加到List中,然后利用语言特性进行反转,再输出即可.

  整个解题过程如下所示.

  /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) { val = x; }
  * }
  */
  class Solution {
      public int[] reversePrint(ListNode head) {
          List<Integer> result = new ArrayList<Integer>();
          while(head != null ) {
              result.add(head.val);
              head = head.next;
          }
          Collections.reverse(result);
          int[] resultArray = new int[result.size()];
          for(int i = 0; i < result.size(); i++) {
              resultArray[i] = result.get(i);
          }
          return resultArray;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(2n)
  • 空间复杂度: O(2n)

  结果如下所示.

  

• 辅助栈法

  我们都知道栈的特性为先进后出,后进先出,所以我们可以先遍历链表把节点入栈,然后依次出栈即可完成整个题解过程.

  /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) { val = x; }
  * }
  */
  class Solution {
      public int[] reversePrint(ListNode head) {
          LinkedList<Integer> stack = new LinkedList<Integer>();
          while(head != null ) {
              stack.addLast(head.val);
              head = head.next;
          }
          int[] resultArray = new int[stack.size()];
          for(int i = 0; i < resultArray.length; i++) {
              resultArray[i] = stack.removeLast();
          }
          return resultArray;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(2n)
  • 空间复杂度: O(2n)

  结果如下所示.