文章目录

1. 题目2. 解题思路2.1 思路12.2 思路22.3 思路3 3. 代码实现3.1 解法一3.2 解法二3.3 解法三 4. 总结5. 参考文献

1. 题目

输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表节点的定义如下：

struct ListNode { int m_nKey; ListNode* m_pNext; }

2. 解题思路

2.1 思路1

每打印一个节点，遍历一次链表。不修改原链表 时间复杂度O(n²)，空间复杂度S(1)。

2.2 思路2

遍历链表，将链表中的节点的值存入一个栈中。然后，遍历栈打印出链表的值。不修改原链表 时间复杂度O(n)，空间复杂度S(n)。

2.3 思路3

先将链表逆序，然后再打印链表。修改原链表 时间复杂度O(n)，空间复杂度S(1)。

3. 代码实现

首先我们创建一个链表：

class ListNode: """定义链表节点""" def __init__(self, value, next=None): self.value = value self.next = next n1 = ListNode(1) n2 = ListNode(2) n3 = ListNode(3) n4 = ListNode(4) n5 = ListNode(5) n6 = ListNode(6) n7 = ListNode(7) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 n5.next = n6 n6.next = n7 head = n1

直接递归实现：

class Solution: def __init__(self): pass def print_list_reversingly(self, head): """每打印一个节点遍历依次链表，递归 :param head: 链表头节点 :return """ # 基线条件 if not head: return self.print_list_reversingly(head.next) print(cur.value)

3.1 解法一

思路1的循环实现：

class Solution: def print_list_reversingly(self, head): """每打印一个节点遍历依次链表，循环 :param head: 链表头节点 :return """ if not head: return record = None # 记录循环的停止节点 p_node = head while p_node: cur = head while cur: if cur.next == record: print(cur.value) record = cur cur = cur.next p_node = p_node.next

3.2 解法二

为了少写点代码，这里我们用一个list来作为一个栈。

思路2的递归实现如下：

g_records = [] class Solution: def print_list_reversingly(self, head): """ 遍历链表，将链表中的节点的值存入一个栈中。然后，遍历栈打印出链表的值。递归实现 :param head: 链表头节点 :return """ # 基线条件 if not head: return self.print_list_reversingly(head.next) g_records.append(head) def print_list_node(self): for node in g_records: print(node.value)

思路2的循环实现如下：

class Solution: def print_list_reversingly(self, head): """ 遍历链表，将链表中的节点的值存入一个栈中。然后，遍历栈打印出链表的值。循环实现 :param head: 链表头节点 :return """ if not head: return records = [] cur = head while cur: records.insert(0, cur) cur = cur.next for node in records: print(node.value)

3.3 解法三

思路3的递归实现：

g_head = None #反转之后的头节点 class Solution: def print_list_reversingly(self, head): """ :param head: 链表头节点 :return """ global g_head # 边界条件 if not head.next: print('head is None') g_head = head return pre = head cur = head.next head.next = None if cur: self.print_list_reversingly(cur) cur.next = pre

思路3的循环实现如下：

class Solution: def print_list_reversingly(self, head): """ :param head: 链表头节点 :return """ # 边界条件 if not head: return pre = head cur = head.next while cur: temp = cur.next cur.next = pre pre = cur cur = temp head.next = None head = pre return head def print_list_node(head): cur = head while cur: print(cur.value) cur = cur.next

4. 总结

通过递归能实现的，通过循环一定也能实现。

递归理解起来简单，写起来容易，但是鲁棒性不好（当递归深度过大，调用栈溢出），而且有可能会重复计算，效率较低。循环理解起来复杂，写起来费劲儿，但是鲁棒性好，而且效率一般比递归要高。

5. 参考文献

[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题