참고
문제해설
NOTE
•
입력값 ⇒ 정렬된 2개의 링크드리스트 배열
•
출력값 ⇒ 2개의 링크드리스트를 순차적으로 병합한 링크드리스
문제 로직고민
NOTE
/**
* 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 list1, ListNode list2) {
}
}
Java
복사
제공된 형식
•
단순하게 2개의 LinkedLIst의 val중 작은 값을 먼저넣는다.
◦
2개의 Linked List 모두 정렬되어 있으므로 가능하다.
◦
val을 넣은 Linked List는 next 해준다.
◦
만약 2개의 배열중 하나를 모두 탐색한다면, 남은 배열값 전부를 넣는다.
작성코드
NOTE
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
return recursive(list1, list2, null);
}
public ListNode recursive(ListNode l1, ListNode l2, ListNode next){
// 2개의 배열을 모두 탐색하면 멈춘다.
if(l1 == null && l2 == null) return null;
// 값은 -100~100 범위이므로, 101을 설정하면 null이 아닌 val값이 무조건 들어간다.
int l1Val = 101;
int l2Val = 101;
// 값 초기화
if(l1 != null) l1Val = l1.val;
if(l2 != null) l2Val = l2.val;
// next 설정
if(l1Val <= l2Val) l1 = l1.next;
else l2 = l2.next;
// 재귀를 통한 ListNode 구현
return new ListNode(Math.min(l1Val,l2Val), recursive(l1, l2, null));
}
}
Java
복사
정답코드
NOTE
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
if (l1 != null) {
curr.next = l1;
l1 = l1.next;
}
if (l2 != null) {
curr.next = l2;
l2 = l2.next;
}
return dummy.next;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
재귀함수를 사용하지 않아 메모리적으로 조금더 효율적인거 같다.
•
개인적으로 2MB밖에 차이안나서 가독성면에서 더 좋은 재귀함수쪽 구현이 더 좋은거 같다.