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 {
}