输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
一解
# 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]:
result = []
while head != None:
result.insert(0, head.val)
head = head.next
return result
-
执行用时：48ms，在所有 Python3 提交中击败了 65.22% 的用户
-
内存消耗：16.4MB，在所有 Python3 提交中击败了 28.53%的用户
题目很简单，但有一种reverse解法，时间比我短很多：
# 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]:
list1 = []
while head:
list1.append(head.val)
head = head.next
list1.reverse()
return list1
-
执行用时：32ms，在所有 Python3 提交中击败了 99.38%的用户
-
内存消耗：16.2MB，在所有 Python3 提交中击败了 70.409%的用户
Python 中insert比reverse效率低在哪？
从 cpython 上找到了源码：
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
assert((size_t)n + 1 < PY_SSIZE_T_MAX);
if (list_resize(self, n+1) < 0)
return -1;
if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
if (where > n)
where = n;
items = self->ob_item;
// 关键地方，每次 insert ，都要将元素向后迁移
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
return 0;
}
每次 insert ，都要将元素向后迁移，这是典型的数组插入实现（我课上有讲），解法一频繁调用 insert ，导致元素频繁后移。
那么 reverse 如何实现？
使用了双指针，进行两两替换：
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
assert(lo && hi);
--hi;
while (lo < hi) {
PyObject *t = *lo;
*lo = *hi;
*hi = t;
++lo;
--hi;
}
}
综上，频繁使用 reverse ，其效率比只用一次 insert 要低很多。