Maximum Twin Sum of a Linked List
给一个链表, 定义twin sum是前后对应的两个node的和, 求最大的twin sum.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int pairSum(ListNode head) { ListNode p = head; ListNode m = mid(head); ListNode r = rev(m); int res = 0; while(p != null){ res = Math.max(res, p.val + r.val); p = p.next; r = r.next; } return res; } private ListNode rev(ListNode head) { ListNode newHead = null; while(head != null){ ListNode next = head.next; head.next = newHead; newHead = head; head = next; } return newHead; } private ListNode mid(ListNode head) { ListNode dF = new ListNode(0); ListNode sF = new ListNode(0); dF.next = head; sF.next = head; while(dF.next != null && dF.next.next != null){ sF = sF.next; dF = dF.next.next; } return sF; } } |