오늘의 문제는 Merge Two Sorted Lists입니다.
문제 설명
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a 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.
2개의 정렬된 리스트들이 있고 이를 합쳐서 하나의 정렬된 리스트로 만들라는 의미이다.
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.
처음에 이 문제를 보고 ListNode 인데..? LinkedList가 아니라..? 라고 생각하며 어떻게 구현된 것인지 좀 구조체가 헷갈렸다.
// 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; }
// }
solution에 기본적으로 적혀있던 구현된 ListNode를 보니 각 노드들에 next 정보가 있기 때문에 이를 활용해 찾아갈 수 있는 것이라고 생각하였고 , list1 과 list2의 val들을 비교해가며 mergeList에 넣으면 해결할 수 있었다.
다른 것들은 다 이해가 되긴 했는데.. 왜 firstList를 먼저 초기화 시켜주고 mergeList = firstList로 받아야하는 진 잘 모르겠다.. print시켜보니 mergeList는 (4,4)가 나왔고.. mergeList.next 는 4가 나왔다. 이를 보니 점점 줄어드는 것 같길래 맨 처음의 mergeList 쪽을 가리키면 나올 것 같아서 firstList.next로 해보니 내가 원하는 정답이 나왔고
하기와 같이 구현하였다.
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) {
return list2;
}
if(list2 == null) {
return list1;
}
ListNode firstList = new ListNode();
ListNode mergeList = firstList;
while (list1 != null && list2 != null) {
if(list1.val <= list2.val) {
mergeList.next = list1;
list1 = list1.next;
}else {
mergeList.next = list2;
list2 = list2.next;
}
mergeList = mergeList.next;
}
if(list1 == null) {
mergeList.next = list2;
}else {
mergeList.next = list1;
}
return firstList.next;
}
의문 사항에 대해서는 추후 스터디 시간에 스터디원분들과 함께 이야기해봐야겠다.
스터디원분들과 함께 이야기하고 생각해보니 firstList라는 것으로 초기화 해주지 않으면 mergeList는 자신의 헤드를 가리킬수 없게 되기 때문에 맨 처음을 가리켜줄 firstList가 있어야한다. firstList 부터 차례로 찾아나가야 내가 원하는 모든 수를 얻을 수 있었다. 이게 바로 스터디의 힘인 것 같다. 혼자 했다면.. 왜 저러지..? 뭐지..? 하고 그냥 넘어갔을 것 같은데 다른 분들과 함께 이야기하고 생각하다보니 깨닫게 되었다.
