Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
统计单链表前后对应位置的和,输出最大的和
先用快慢两个指针,快指针每次前进两个node,这样定位到单链表中心位置,然后翻转后一半链表的指针(很巧妙,思路参考Discussion)


 1 #2130
 2 #Runtime: 1108 ms (Beats 78.1%)
 3 #Memory: 72.2 MB (Beats 80.63%)
 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 pairSum(self, head):
12         """
13         :type head: Optional[ListNode]
14         :rtype: int
15         """
16         node_slow, node_fast = head, head
17         ans = 0
18         while node_fast and node_fast.next:
19             node_fast = node_fast.next.next
20             node_slow = node_slow.next
21         node_cur, node_pre = node_slow, None
22         while node_cur:
23             node_cur.next, node_pre, node_cur = node_pre, node_cur, node_cur.next
24         while node_pre:
25             ans = max(ans, head.val + node_pre.val)
26             node_pre = node_pre.next
27             head = head.next
28         return ans

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