二叉树的题目告一段落，后面陆续做了些基础的题；感觉没有什么好记录的。
这次是一个非常基础题目用递归和遍历两个方法反转一个单链队列。如下所示。
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
递归的方法，考虑了下其实方法很多，我想了比较简单的，就是取出第一个节点，放在后续节队列的最后，如此循环递归直到只有一个节点位置。代码是很好写，就是效率太低，提交运行时间1008ms，实在是，主要每次一个节点排序，都要遍历整条队列，其实应该有更好的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# 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: if head == None or head.next == None: return head node = self.reverseList(head.next) head.next = None checknode = node while checknode.next != None: checknode = checknode.next checknode.next = head return node |
遍历方法也很简单，就是新建一个队列做栈，把单链队列的按照顺序放入，然后反向推出节点，重组队列返回即可。提交运行时间34ms, 效率高很多。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# 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: if head == None: return head nodeStack = [] while head != None: nodeStack.append(head) head = head.next print(len(nodeStack)) newHead = nodeStack.pop() point = newHead while nodeStack != []: point.next = nodeStack.pop() point = point.next point.next = None return newHead |
原文：https://www.cnblogs.com/chenguopa/p/15239883.html