[LeetCode] 2130. Maximum Twin Sum of a Linked List(Kotlin)

[LeetCode] 2130. Maximum Twin Sum of a Linked List(Kotlin)

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

풀이 1

• Linked List 자료구조 List로 변환 후, 인덱스로 접근하여 PairSum 계산

import kotlin.math.*

class Solution {
    fun pairSum(head: ListNode?): Int {
        val headList = convertHeadToList(head)
        val n = headList.size
        var maxPairSum = 0
        for(left in 0 until n/2){
            maxPairSum = max(maxPairSum, headList[left] + headList[n-left-1])
        }
        return maxPairSum
    }

    private fun convertHeadToList(head: ListNode?):List<Int>{
        val headList = mutableListOf<Int>()
        var curNode = head
        while(curNode != null){
            headList.add(curNode.`val`)
            curNode = curNode.next
        }
        return headList.toList()
    }
}

풀이2

• Linked List 자료구조 양방향 Linked List로 변환 후, 포인터로 접근하여 PairSum 계산
• 코드는 풀이 1에 비해 복잡해졌지만, 효율은 크게 다르지 않다.

data class BiDirNode(
    val value : Int,
    var prev: BiDirNode? = null,
    var next: BiDirNode? = null
)

class Solution {

    fun pairSum(head: ListNode?): Int {
        if(head == null) return 0 //not reached
        val biDirNodePair = convertHeadToBiDirList(head!!)

        var left = biDirNodePair.first
        var right = biDirNodePair.second
        var maxPairSum = left.value + right.value

        // given linked list size: [2, 10^5]  
        while(left.next != right){
            left = left.next!!
            right = right.prev!!
            maxPairSum = max(maxPairSum, left.value + right.value)
        }
        return maxPairSum
    }

    // convert Linked List rto bi-directional Linked List
    // return head & tail of bi-directional linked list
    fun convertHeadToBiDirList(head:ListNode): Pair<BiDirNode, BiDirNode>{
        var biDirHead: BiDirNode? = null // head of bi-directional linked list

        // ListNodes to iterate linked list
        var curNode: ListNode = head
        var fastNode:ListNode? = head.next

        var prevBiDirNode: BiDirNode? = null
        while(true){
            // convert current ListNode to BiDirNode
            val curBiDirNode = BiDirNode(
                value = curNode.`val`,
                prev = prevBiDirNode
            )
            prevBiDirNode?.next = curBiDirNode

            // initialize head of bi-directional linked list
            if(biDirHead == null) biDirHead = curBiDirNode

            prevBiDirNode = curBiDirNode 
            // move to next ListNode
            if(fastNode == null) break
            curNode = fastNode
            fastNode = fastNode.next
        }
        prevBiDirNode!!.next = null // tail of bi-directional linked list

        return biDirHead!! to prevBiDirNode!!
    }
}