Maximum Twin Sum of a Linked List LeetCode solution in Java

1
/**
2
 * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode() {}
3
 * ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val;
4
 * this.next = next; } }
5
 */
6
class Solution {
7
  public int pairSum(ListNode head) {
8
    if (head == null) {
9
      return 0;
10
    }
11
    if (head.next == null) {
12
      return head.val;
13
    }
14
    ListNode slow = head;
15
    ListNode fast = head;
16
    while (fast != null && fast.next != null) {
17
      slow = slow.next;
18
      fast = fast.next.next;
19
    }
20
    slow = reverse(slow);
21
    fast = head;
22
    int sum = Integer.MIN_VALUE;
23
    while (slow != null) {
24
      sum = Math.max(slow.val + fast.val, sum);
25
      slow = slow.next;
26
      fast = fast.next;
27
    }
28
    return sum;
29
  }
30

31
  public ListNode reverse(ListNode node) {
32
    if (node == null) {
33
      return null;
34
    }
35
    ListNode current = node;
36
    ListNode previous = null;
37
    while (current != null) {
38
      ListNode next = current.next;
39
      current.next = previous;
40
      previous = current;
41
      current = next;
42
    }
43
    return previous;
44
  }
45
}