您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
二叉树的题目告一段落,后面陆续做了些基础的题;感觉没有什么好记录的。
这次是一个非常基础题目用递归和遍历两个方法反转一个单链队列。如下所示。
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
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。