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

题目

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1. 修改链表

最简答直接的办法就是修改链表，首先让指针指向最后，然后依次将链表反向链接，双指针翻转链表比较简单。

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p1 = None 
        p2 = head

        while p2 is not None:
            t = p2.next
            p2.next = p1
            p1 = p2
            p2 = t
        return p1

2. 顺序读，逆序存

因为输出要求是存在数组中，那么很容易想到，先遍历一遍得到链表大小，然后开辟一个同样大小的数组，然后从后往前存。

# 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 []

        count = 0
        head_p = head
        while head_p is not None:
            count += 1
            head_p = head_p.next
        l = [0]*count

        for i in range(count):
            l[count-i-1] = head.val
            head = head.next   
        return l

3. 利用栈的特点或者递归

用python实现的话比较简单：

总结

比较简单的类型。