(LeetCode) 21. Merge Two Sorted Lists

Merge Two Sorted Lists

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Linked List
• 난이도 : Easy

Problem

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2

Input: l1 = [], l2 = [0]
Output: [0]

Example 3

Input: head = []
Output: []

Constraints

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

Solution

Exapnder

/**
 * 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(l1: ListNode?, l2: ListNode?): ListNode? {
        if (l1 == null) {
            return l2
        }
        if (l2 == null) {
            return l1
        }
        var list1 = l1
        var list2 = l2

        var first = ListNode(0)
        var result = first
        while (list1 != null && list2 != null) {
            if (list1.`val` > list2.`val`) {
                result.next = list2
                list2.next.also { list2 = it }
            } else {
                result.next = list1
                list1 = list1.next
            }
            result = result.next
        }

        if (list1 == null) {
            result.next = list2
        } else if (list2 == null) {
            result.next = list1
        }
        return first.next
    }
}

Point of Thinking

• 두 개의 리스트 중 하나가 비어있다면 다른 하나의 리스트를 ealry return
• 임의의 노드를 생성하여 각 리스트의 val 값을 비교하여 붙여주고, 하나의 리스트를 먼저 순회하게 된 경우 나머지 리스트를 뒤에 붙여준다.