Daily Algorithm - Merge Two Sorted Lists

Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

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

Solution

• 풀이를 위한 접근 방식은 쉽다. 더미 ListNode를 만들어 list1과 list2의 값을 하나씩 돌면서 보다 작은 수를 더미에 넣으면 된다.
• 하지만 이 풀이에서 내가 가장 헤맨 부분은 tail과 dummy의 관계였다.
  1. tail은 dummy의 주소값을 가지고 있으므로 tail의 next에 값을 넣는 것은 dummy의 next에 값을 넣는 것과 같다.
  2. tail.next를 tail에 다시 할당해줌으로써 다음 next를 추가할 꼬리 값을 갱신해준다.
• 위의 두가지를 이해하는 것이 이 풀이의 핵심인 것 같다.

/**
 * 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? {
        val dummy = ListNode(0)
        var tail = dummy
        
        var curr1 = list1
        var curr2 = list2
        
        while (curr1 != null && curr2 != null) {
            if (curr1.`val` < curr2.`val`) {
                tail.next = curr1
                curr1 = curr1.next
            } else {
                tail.next = curr2
                curr2 = curr2.next
            }
            tail = tail.next
        }
        
        if (curr1 != null) {
            tail.next = curr1
        } else if (curr2 != null) {
            tail.next = curr2
        }
        
        return dummy.next
    }
}