2130. Maximum Twin Sum of a Linked List

[antop-dev]

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

[antop-dev]

LinkedList를 ArrayList로 변경 후 투 포인터로 풀었다. 느리다...

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun pairSum(head: ListNode?): Int {
        if (head == null) return 0 // can't null
        // linked list → array list
        val list = mutableListOf<Int>()
        var node: ListNode? = head
        while (node != null) {
            list += node.`val`
            node = node.next
        }
        // sum twin
        var max = 0
        for (i in 0 until (list.size / 2)) {
            val sum = list[i] + list[list.size - 1 - i];
            max = maxOf(max, sum)
        }
        return max
    }
}

[antop-dev]

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/solutions/5538770/3ms-solution-beat-100-simple-approach-o-1-sc/

LinkedList의 반을 역순으로 참조하게 만든다.

LinkedList 참조를 뒤집기

위와 같이 3개의 노드가 있을 때 노드를 뒤집는 방법이다.

var prev: ListNode? = null
var node = head
while (node != null) {
    val next = node.next // ①
    node.next = prev // ②
    prev = node // ③
    node = next // ④
}
// prev로 역순 탐색
while (prev != null) {
    println("prev = ${prev.`val`}")
    prev = prev.next
}

그리고 반만 탐색하기 위해서 두개씩 건너띄도록 한다.

var node = head
while (node != null) {
    node = node.next?.next
}

이 두 개를 이용해서 푼다.

Kotlin:

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun pairSum(head: ListNode?): Int {
        var prev: ListNode? = null
        var slow = head
        var fast = head
        while (fast != null) {
            fast = fast.next?.next
            val next = slow?.next
            if (slow != null) slow.next = prev
            prev = slow
            slow = next
        }

        var ans = 0
        while (prev != null && slow != null) {
            ans = maxOf(ans, prev.`val` + slow.`val`)
            prev = prev.next
            slow = slow.next
        }
        return ans
    }
}

[antop-dev]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        prev = None
        slow = head
        fast = head
        while fast is not None:
            fast = fast.next.next
            _next = slow.next
            slow.next = prev
            prev = slow
            slow = _next

        ans = 0
        while prev is not None:
            ans = max(ans, prev.val + slow.val)
            prev = prev.next
            slow = slow.next

        return ans