[Linked List, Medium] Maximum Twin Sum of a Linked List

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/description/?envType=study-plan-v2&envId=leetcode-75

i번째는 (n-i-1)번째와 짝이므로 왼쪽 끝과 오른쪽 끝에서부터 투포인터 탐색으로 볼 수 있다.

그러나 단방향으로 연결된 Linked List라는 특성 상 단순히 정순포인터, 역순포인터로 조회하기는 어렵다.

따라서 전체 길이를 구하고, 그 절반을 구한 뒤에 전체 리스트에서 절반을 자르면 순회하기가 쉽다.

또한 잘린 뒷부분은 역순으로 정렬되어 있어야 단방향 (.next)조회가 용이하기 때문에
결국은 Reverse Linked List 문제의 응용이라고 볼 수 있다.

class Solution {
    public int pairSum(ListNode head) {
        
        int max = Integer.MIN_VALUE;

        ListNode current = head;
        int n = 1;
        while (current.next != null) {
            current = current.next;
            n++;
        }

        int half = n / 2;

        int mid = 1;
        current = head;
        while (mid < half) {
            current = current.next;
            mid++;
        }
        // 리스트 끊기
        ListNode reverseHead = current.next;
        current.next = null;

        ListNode prev = null;
        ListNode next = null;
        while (reverseHead != null) {
            next = reverseHead.next;
            reverseHead.next = prev;
            prev = reverseHead;

            reverseHead = next;
        }
        reverseHead = prev;

        for (int i=0; i<half; i++) {
            int sum = head.val + reverseHead.val;
            max = Math.max(sum, max);
            
            head = head.next;
            reverseHead = reverseHead.next;
        }
        return max;
    }
}

이 문제도 마찬가지로 solution의 다른 사람들 풀이를 참고해 보면
mid 노드를 구하기 위해 n을 구하고, 또 n / 2번만큼 순회하지 않아도 되고
slow, fast로 slow는 slow.next, fast는 fast.next.next 조건으로 while 돌려주면
fast는 두 배씩 증가하기 때문에 while종료 순간 slow는 mid가 됨을 보장할 수 있다.

어찌되었건 최종적으로는 절반의 뒷부분을 역순 정렬한 뒤 n/2번만큼 순회하는 논리는 동일하다.