👀 문제
https://leetcode.com/problems/merge-two-sorted-lists/
👊 도전
1. 설계
- l1, l2를 비교하며 같거나 작은 값을 result에 넣는다.
- 둘 중 하나라도 끝나면 나머지 리스트를 뒤에 붙인다.
2. 구현
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
*
* @author HEESOO
*
*/
/**
* 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 l1, ListNode l2) {
// 리스트 하나만 있다면 그걸 리턴
if(l1==null) return l2;
else if(l2==null) return l1;
ListNode result=new ListNode(0);
ListNode temp=result; // 포인터
while(true){
if(l1==null || l2==null) break; // 둘 중 하나라도 끝나면 종료
int val1=l1.val;
int val2=l2.val;
if(val1<=val2){ // l1 값을 선택
temp.next=new ListNode(val1);
temp=temp.next;
l1=l1.next;
}
if(val1>=val2){ // l2를 선택
temp.next=new ListNode(val2);
temp=temp.next;
l2=l2.next;
}
}
// Merge하고 남은 리스트를 뒤에 연결
while(l1!=null){
temp.next=new ListNode(l1.val);
temp=temp.next;
l1=l1.next;
}
while(l2!=null){
temp.next=new ListNode(l2.val);
temp=temp.next;
l2=l2.next;
}
return result.next;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 두 리스트 중 하나가 끝날 때 까지 숫자를 체크, result에 넣는다
- 현재 위치에서 val1, val2를 찾고 둘 중 작은 값을 result에 넣는다. 이때 두 값이 같을 수도 있으므로 작거나 같아야 한다.
- l1의 값을 넣기 위해서는 val1<=val2여야 한다. 넣은 후 l1는 다음 원소로 이동, temp도 다음으로 이동한다.
- l2도 같다.
- 둘 중 하나라도 리스트 순회가 끝나면 while문을 나온다.
- 남은 리스트를 temp 뒤에 연결한다
- l2 순회가 끝난 경우라면 처음 while문에서 l1의 남은 값들을 temp에 연결한다.
- l1이 끝나서 while을 나온 것이라면 두 번째 while문에서 l2의 남은 값들을 temp에 넣는다.
- 마지막으로 result.next의 리스트를 리턴한다.