[Linked List][Medium] 2130. Maximum Twin Sum of a Linked List

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

Maximum Twin Sum of a Linked List - LeetCode

 

Q. 앞과 뒤로부터 각각 같은 순서의 노드를 pair로 묶었을때, 이 들 노드 중 최대합을 반환하라.

 

Solution. 

 Leetcode 문제는 영어로 되어 있어서 언제나 필요이상으로 복잡하다고 느껴진다. 하지만, 제대로 해석하면 문제자체는 명확하고 간결하다. 그리고 이것이 항상 문제 풀이전 우선시 되어야 한다. 

 

 단일 링크드 리스트는 prev로 가는 노드가 없기때문에 어떻게 이전 노드로 역진행하는가에 대한 문제가 항상 나온다. 이 문제도 그런류 이다. 

 단순히 전체 노드를 copy해서 뒤집으면 간단하지만, 그러면 SC가 추가 O(N)이 소모케 되며, 이는 바라는 바가 아니다. 

  따라서 반은 정진행, 나머지 반만 역진행 하면 됨에 포커스를 맞춘다. 

  

 노드의 중심 노드를 찾는 문제는 이미 해 봤다. 

 노드를 뒤집는 문제도 이미 해 봤다. 

 그렇다면 노드의 중심에서 이전노드들은 뒤집고, 이후로 진행하면서 하나씩 더해 보면 결국 우리가 원하는 pair노드의 합을 순회하면서 얻는 것이 될 것이다. 

 

int pairSum(ListNode* head)
{
    // 리스트의 중심을 찾는다.
    ListNode* fast = head;
    ListNode* slow = head;
    ListNode* prevSlow = NULL;
    while (fast != NULL && fast->next != NULL)
    {
        prevSlow = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

	// 전반부는 뒤집는다.
    ListNode* rightHead = slow;
    ListNode* leftHead = prevSlow;
    ListNode* prev = NULL;
    slow = head;
    while (slow != rightHead)
    {
        ListNode* next = slow->next;
        slow->next = prev;
        prev = slow;
        slow = next;
    }

	// 전반, 후반 파트를 진행해 나가면서 pair node의 합을 구한다.
    int ret = 0;
    ListNode* right = rightHead;
    ListNode* left = leftHead;
    while (right != NULL)
    {
        ret = max(ret, right->val + left->val);
        right = right->next;
        left = left->next;
    }
    return ret;
}