每日一刷之劍指Offer(5)從尾到頭列印鍊表

題目快速預覽解題思路

（1）遞歸遍歷鍊表輸出

#encoding:utf-8
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class SingleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def add(self, data):
        node = ListNode(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next =node
            self.tail = node
 
    def iter(self):
        if not self.head:
            return
        cur = self.head
        yield cur.val
        while cur.next:
            cur = cur.next
            yield cur.val
 
class Solution:
    # 返回從尾部到頭部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        if listNode is None:
            return []
        return self.printListFromTailToHead(listNode.next) + [listNode.val]
 
if __name__=="__main__":
    link_list = SingleLinkedList()
    for i in range(5):
        link_list.add(i)
 
    for node in link_list.iter():
        print("node is {0}".format(node))
 
    solution = Solution()
    # Python遞歸實現。
    print(solution.printListFromTailToHead(link_list.head))
（2）順序遍歷鍊表，反轉遍歷的結果
def printListFromTailToHead(self, listNode):
    if not listNode:
        return []
    res = []
    index = listNode
    while index:
        res.append(index.val)
        index = index.next

    return res[::-1]
（3）輔助棧法
解題思路：
鍊表特點：只能從前至後訪問每個節點。
題目要求：倒序輸出節點值。
這種先入後出的需求可以藉助棧來實現。
算法流程：
入棧：遍歷鍊表，將各節點值push入棧。(Python使用append()方法，Java藉助LinkedList的addLast()方法)。
出棧：將各節點值pop出棧，存儲於數組並返回。(Python直接返回stack的倒序列表，Java新建一個數組，通過popLast()方法將各元素存入數組，實現倒序輸出)。
複雜度分析：
時間複雜度O(N)：入棧和出棧共使用O(N)時間。
空間複雜度O(N)：輔助棧stack和數組res共使用O(N)的額外空間。
def printListFromTailToHead(self, listNode):
    stack = []
    while listNode:
        stack.append(listNode.val)
        listNode = listNode.next
    return stack[::-1]
（4）鍊表原地反轉
def printListFromTailToHead(self, listNode):
    if not listNode:
        return []

    p1 = listNode
    p2 = listNode.next
    p3 = listNode.next.next
    while p2:
        p3 = p2.next
        p2.next = p1
        p1 = p2
        p2 = p3
    listNode.next = None
    listNode = p1

    res = []
    while listNode:
        res.append(listNode.val)
        listNode = listNode.next

    return res
Reference：
【1】Python數據結構-鍊表。地址：http://zhaochj.github.io/2016/05/12/2016-05-12-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E9%93%BE%E8%A1%A8/
點擊左下角閱讀原文即可快速跳轉至牛客網在線提交地址，大家快去提交代碼哦！
                

讚賞一下，讓分享更有動力！