126일 (2130. Maximum Twin Sum of a Linked List) 리스트조작

In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

• For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

 

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6. 

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7. 

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

 

Constraints:

• The number of nodes in the list is an even integer in the range [2, 10^5].
• 1 <= Node.val <= 10^5

 

- 접근방법

 

역순으로 참조가 되지않고 인덱스가 존자하지 않는 리스트 노드의 양 끝의 값의 합 중 최댓값을 리턴하면 된다.

포인터로 리스트를 좌우 2개로 이등분하고, 오른쪽리스트를 역순으로 노드를 엮을 것이다.

그리고나서 왼쪽리스트의 값과 오른쪽리스트의 역순의 값의 합 중 최댓값을 찾아 리턴할 것이다.

 

1. 연결리스트의 길이가 짝수이므로 리스트를 이등분하였다면 오른쪽 리스트의 시작점을 찾는다. (123|456일때 4)

→ ListNode mid가 가르키는 값이 노드의 중간+1 의 인덱스에 해당.

 

2. 정순으로 이어지는 리스트를 역순으로 만들기 위해 포인터 역할을 하는 reverseHead, nextnode를 초기화한다.

→ 123456 일때, 4번에서 6번까지 탐색하면서 새로운 노드 2가지로 456을 654로 연결되는 리스트로 만들 것이다.

 

3.  리스트를 2등분 시 우측의 리스트를 역순의 연결리스트로 조합하였다.

→ 123456 일때 123 그리고 654가 되었다.

 

4. 123과 654를 (1,4) (2,5) (3,6) 순으로 더하여 최댓값을 리턴한다.

 

 

-  코드

class Solution {
    public int pairSum(ListNode head) {
        ListNode mid = head;
        ListNode end = head;
        int answer = 0;

        while(end != null && end.next != null) { /// 1
            mid = mid.next;
            end = end.next.next;
        }

        ListNode reverseHead = null; // 2
        ListNode nextNode = null;

        while(mid != null) { // 3
            nextNode = mid.next;
            mid.next = reverseHead;
            reverseHead = mid;
            mid = nextNode;
        }

        while(true) { // 4
            if(head == null || reverseHead == null) break;
            answer = Math.max(head.val+reverseHead.val, answer);
            head = head.next;
            reverseHead = reverseHead.next;
        }

        return answer;
    }

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

 

3번처럼 연결리스트를 역방향의 새로운 리스트를 만드는게 참 헷갈렸다..

stack이나 map, StringBuilder 등을 사용하면 매우 느리다.. 

문제 카테고리도 stack으로 되어있지만 리스트조작이 태그가 아닐까 싶다..

 

 

 

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list

LeetCode - The World's Leading Online Programming Learning Platform