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

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

示例 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 中insertreverse效率低在哪?

从 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 如何实现?

image

使用了双指针,进行两两替换:


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 要低很多。