PS/Medium

2130. Maximum Twin Sum of a Linked List (Two Point)

우봉수 2023. 5. 17. 20:56

<아이디어>

구현 문제를 푸는 방법처럼 노드의 맨끝과 맨처음에서 점차 한 칸씩 앞으로 이동 하면서 합계를 구하고 최대값을 반환

맨끝에 존재하는 노드에서 한 칸씩 앞으로 가는 방법은 재귀를 이용하여 구현

 

<풀이 코드>

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 {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    private int ans=Integer.MIN_VALUE;
    private ListNode start;
    // 제일 뒤에 노드와 제일 앞의 노드의 합계를 구하고 ans에 최대값을 저장
    public void addEachStartNodeEndNode(ListNode end){
        // 제일 맨 끝 노드로 이동
        if(end==null)
            return;
        addEachStartNodeEndNode(end.next);

        ans = Math.max(ans,(end.val+start.val));
        start = start.next;
    }
    public int pairSum(ListNode head) {
        start = head;
        ListNode end = head;
        addEachStartNodeEndNode(end);
        return ans;
    }
}
public class MaximumTwinSumofaLinkedList {
}