十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
二叉树的题目告一段落,后面陆续做了些基础的题;感觉没有什么好记录的。
创新互联建站-专业网站定制、快速模板网站建设、高性价比回民网站开发、企业建站全套包干低至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