Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
链表反转,用迭代和递归两种方式实现,发现递归版快很多

迭代版
 1 #206
 2 #Runtime: 53 ms
 3 #Memory Usage: 15.6 MB
 4 
 5 # Definition for singly-linked list.
 6 # class ListNode(object):
 7 #     def __init__(self, val=0, next=None):
 8 #         self.val = val
 9 #         self.next = next
10 class Solution(object):
11     def reverseList(self, head):
12         """
13         :type head: ListNode
14         :rtype: ListNode
15         """
16         p = None
17         while head != None:  
18             nxt = head.next
19             head.next = p
20             p = head
21             head = nxt
22         return p  

递归版
 1 #206
 2 #Runtime: 26 ms
 3 #Memory Usage: 18.9 MB
 4 
 5 # Definition for singly-linked list.
 6 # class ListNode(object):
 7 #     def __init__(self, val=0, next=None):
 8 #         self.val = val
 9 #         self.next = next
10 class Solution(object):
11     def DFS(self, head, p):
12         if head == None:
13             return p
14         nxt = head.next
15         head.next = p
16         p = head
17         head = nxt
18         return self.DFS(head, p)
19         
20     def reverseList(self, head):
21         """
22         :type head: ListNode
23         :rtype: ListNode
24         """
25         p = None
26         return self.DFS(head, p) 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理