Question

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

题目描述

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

 

示例 1：

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

 

限制：

0 <= 链表长度 <= 10000

解法

方法一：顺序遍历 + 反转

我们可以顺序遍历链表，将每个节点的值存入数组中，然后将数组反转。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为链表的长度。

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, x):
#     self.val = x
#     self.next = None


class Solution:
  def reversePrint(self, head: ListNode) -> List[int]:
    ans = []
    while head:
      ans.append(head.val)
      head = head.next
    return ans[::-1]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public int[] reversePrint(ListNode head) {
    Deque<Integer> stk = new ArrayDeque<>();
    for (; head != null; head = head.next) {
      stk.push(head.val);
    }
    int[] ans = new int[stk.size()];
    for (int i = 0; !stk.isEmpty(); ++i) {
      ans[i] = stk.pop();
    }
    return ans;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> reversePrint(ListNode* head) {
    if (!head) return {};
    vector<int> ans = reversePrint(head->next);
    ans.push_back(head->val);
    return ans;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func reversePrint(head *ListNode) (ans []int) {
  for ; head != nil; head = head.Next {
    ans = append(ans, head.Val)
  }
  for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    ans[i], ans[j] = ans[j], ans[i]
  }
  return
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function reversePrint(head: ListNode | null): number[] {
  let ans: number[] = [];
  for (; !!head; head = head.next) {
    ans.unshift(head.val);
  }
  return ans;
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//   ListNode {
//     next: None,
//     val
//   }
//   }
// }
impl Solution {
  pub fn reverse_print(head: Option<Box<ListNode>>) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    let mut cur = head;
    while let Some(node) = cur {
      arr.push(node.val);
      cur = node.next;
    }
    arr.reverse();
    arr
  }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *   this.val = val;
 *   this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function (head) {
  let ans = [];
  for (; !!head; head = head.next) {
    ans.unshift(head.val);
  }
  return ans;
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   public int val;
 *   public ListNode next;
 *   public ListNode(int x) { val = x; }
 * }
 */
 public class Solution {
   public int[] ReversePrint(ListNode head) {
     List<int> ans = new List<int>();
     while (head != null) {
       ans.Add(head.val);
       head = head.next;
     }
     ans.Reverse();
     return ans.ToArray();
   }
 }

方法二：递归

我们可以使用递归的方式，先递归得到 head 之后的节点反过来的值列表，然后将 head 的值加到列表的末尾。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为链表的长度。

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, x):
#     self.val = x
#     self.next = None


class Solution:
  def reversePrint(self, head: ListNode) -> List[int]:
    if head is None:
      return []
    ans = self.reversePrint(head.next)
    ans.append(head.val)
    return ans

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public int[] reversePrint(ListNode head) {
    int n = 0;
    ListNode cur = head;
    for (; cur != null; cur = cur.next) {
      ++n;
    }
    int[] ans = new int[n];
    cur = head;
    for (; cur != null; cur = cur.next) {
      ans[--n] = cur.val;
    }
    return ans;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> reversePrint(ListNode* head) {
    vector<int> ans;
    for (; head; head = head->next) {
      ans.push_back(head->val);
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func reversePrint(head *ListNode) (ans []int) {
  if head == nil {
    return
  }
  ans = reversePrint(head.Next)
  ans = append(ans, head.Val)
  return
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//   ListNode {
//     next: None,
//     val
//   }
//   }
// }
impl Solution {
  pub fn reverse_print(head: Option<Box<ListNode>>) -> Vec<i32> {
    let mut cur = &head;
    let mut n = 0;
    while let Some(node) = cur {
      cur = &node.next;
      n += 1;
    }

    let mut arr = vec![0; n];
    let mut cur = head;
    while let Some(node) = cur {
      n -= 1;
      arr[n] = node.val;
      cur = node.next;
    }
    arr
  }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *   this.val = val;
 *   this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function (head) {
  if (!head) {
    return [];
  }
  const ans = reversePrint(head.next);
  ans.push(head.val);
  return ans;
};