LeetCode - 21. Merge Two Sorted Lists [Java], [Kotlin]

• 문제 링크 : 21. Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode

 

# Java

정답(Solution)

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode root = new ListNode();
        ListNode dummy = root;

        while(list1 != null || list2 != null){

            ListNode node = new ListNode();

            if(list1 == null){
                node.val = list2.val;
                list2 = list2.next;
            }else if(list2 == null){
                node.val = list1.val;
                list1 = list1.next;
            }else{
                if(list1.val <= list2.val){
                    node.val = list1.val;
                    list1 = list1.next;
                }else{
                    node.val = list2.val;
                    list2 = list2.next;
                }
            }

            root.next = node;
            root = root.next;
        }

        return dummy.next;
    }
}

 

분석

• 연결 리스트 문제
• Node에 대해서 기본 지식이 있어야 풀 수 있는 문제

 

참고할 만한 정답

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;

      if(list1.val<list2.val)
      {
         list1.next=mergeTwoLists(list1.next,list2);
          return list1;
      }

        else
        {
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }

    }
}

 

비교 분석

• 재귀를 이용하여 풀었다.
• 정답들을 비교해 보니 내 풀이는 while문을 돌때마다 new로 ListNode를 생성해서 메모리를 조금 더 사용했다.

 

# Kotlin

정답(Solution) - Iteration

/**
 * 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 mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        
        var l1 = list1
        var l2 = list2
        
        val head = ListNode()
        var tail = head
        
        while(l1 != null && l2 != null){
            if(l1.`val` < l2.`val`){
                tail.next = l1
                l1 = l1.next
            }else{
                tail.next = l2
                l2 = l2.next
            }
            tail = tail.next
        }
        
        tail.next = l1 ?: l2
        
        return head.next
    }
}

분석

• Java와는 다르게 val는 불변 변수이기 때문에 input을 바로 사용할 수 없고 var로 선언한 변수에 담아서 사용해야 한다.

 

정답(Solution) - Recursion

/**
 * 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 mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        when{
            list1 == null -> return list2
            list2 == null -> return list1
            list1.`val` < list2.`val` -> {
                list1.next = mergeTwoLists(list1.next, list2)
                return list1
            }
            else -> {
                list2.next = mergeTwoLists(list1, list2.next)
                return list2
            }
        }
    }
}