链表

6.从尾到头打印链表

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

方法一 迭代

创建空列表res，将链表值head.val依次存进res，返回翻转后的res

代码

class Solution:

    def reversePrint(self, head: ListNode) -> List[int]:

        res = []

        while head:

            res.append(head.val)

            head = head.next

        return res[::-1]

结果

执行用时 :44 ms, 在所有 Python3 提交中击败了81.86%的用户

内存消耗 :15.1 MB, 在所有 Python3 提交中击败了100.00%的用户

方法二 递归

递归调用函数，将元素从最后开始输出

代码

class Solution:

    def reversePrint(self, head: ListNode) -> List[int]:

        while not head:

            return []

        return self.reversePrint(head.next) + [head.val]

结果

执行用时 :124 ms, 在所有 Python3 提交中击败了18.23%的用户

内存消耗 :22.7 MB, 在所有 Python3 提交中击败了100.00%的用户

18.删除链表的节点

题目

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

head是一个单向链表的头指针，val是给定要删除的值。修改指针位置实现删除链表。

代码

class Solution:

    def deleteNode(self, head: ListNode, val: int) -> ListNode:

        if head.val == val:

            return head.next

        dummy = ListNode(0)   # dummy为一个节点

        dummy.next = head

        pre, cur = dummy, dummy.next  # 当前节点与指针

        while cur:    # 当指针不为None

            if cur.val == val:  # 当节点的指针指向val

                pre.next = cur.next # 将指针修改

                return dummy.next   # 返回head

            else:

                pre = pre.next

                cur = cur.next