LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정렬된 두 연결리스트의 헤드 노드 list1, list2
2. output: 두 연결리스트의 모든 노드를 포함한 정렬된 연결리스트 리턴

• 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.

Idea

non-decreasing oreder라는 용어를 쓰다니..

연결리스트가 2개로 고정되어 있고, 이미 두 연결리스트가 정렬된 상태이므로 단순 비교를 통해 삽입만 해주면 된다 → 시간 복잡도: n

Solution

1. 새로운 연결리스트에 더 작은 값 삽입

   /**
    * 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 answer = ListNode(0)
           var cursorAnswer = answer
           var cursor1 = list1
           var cursor2 = list2
           while (true) {
               if (cursor1 == null) { // list1에 남은 원소 없음
                   cursorAnswer?.next = cursor2
                   break
               }
               if (cursor2 == null) { // list2에 남은 원소 없음
                   cursorAnswer?.next = cursor1
                   break
               }
               // 더 작은 값 삽입
               if (cursor1!!.`val` <= cursor2!!.`val`) {
                   cursorAnswer?.next = cursor1
                   cursorAnswer = cursorAnswer!!.next
                   cursor1 = cursor1!!.next
               } else {
                   cursorAnswer?.next = cursor2
                   cursorAnswer = cursorAnswer!!.next
                   cursor2 = cursor2!!.next
               }
           }
           return answer.next
       }
   }
   

   시간 복잡도: 두 연결리스트 순회 = n

   

Point

1. list1에 list2의 노드를 오름차순에 맞춰 삽입하는 방법으로 in place 정렬 가능