统计单链表前后对应位置的和,输出最大的和
先用快慢两个指针,快指针每次前进两个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