(LeetCode) 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

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

Example 2

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

Example 3

1
2
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* 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 값을 비교하여 붙여주고, 하나의 리스트를 먼저 순회하게 된 경우 나머지 리스트를 뒤에 붙여준다.