刷题系列-用递归和遍历两个方法反转一个单链队列

二叉树的题目告一段落，后面陆续做了些基础的题；感觉没有什么好记录的。

创新互联建站-专业网站定制、快速模板网站建设、高性价比回民网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式回民网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖回民地区。费用合理售后完善，10余年实体公司更值得信赖。

这次是一个非常基础题目用递归和遍历两个方法反转一个单链队列。如下所示。

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

递归的方法，考虑了下其实方法很多，我想了比较简单的，就是取出第一个节点，放在后续节队列的最后，如此循环递归直到只有一个节点位置。代码是很好写，就是效率太低，提交运行时间1008ms，实在是，主要每次一个节点排序，都要遍历整条队列，其实应该有更好的。

# 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, 效率高很多。

# 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

网页标题：刷题系列-用递归和遍历两个方法反转一个单链队列
文章分享：http://shouzuofang.com/article/ghjhgo.html