이지 난이도 문제입니다. Sorted List를 보자마자. 공포가 엄습해 옵니다..
출처: https://leetcode.com/problems/merge-two-sorted-lists/description/
처음엔 문제가 읽히지 않더군요.. 딴짓도 했습니다. 나한테 코딩 테스트가 맞지 않나? 하면서 남들이 코딩테스트를 어떻게 생각하는지 구글링도 해줍니다. 역시, 저와같은 사람들이 많네요(코딩 테스트 공포증)..
다 비슷하구나 생각하며 마음을 다잡습니다. 최근에 cs study를 진행하며 운영체제와 자료구조를 공부하며 링크드 리스트를 봤습니다. 역시, 뭐든 공부해두면 쓸 데가 있는 것 같네요.
처음엔 sort도 해줘야 하나 했지만 이미 되어 있네요.. 공포증에 의해서 문제도 잘 읽히지 않습니다.
다시 제대로 보니까 ListNode의 선언이 어떻게 되어 있나 보이더라고요.
나름 몇 달간 자바를 공부해서 이해가 잘 됩니다.
사실 솔루션을 잠깐 봤습니다. 하지만, 이해가 되지 않아서 문제를 도전해 봅니다.
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 1. 이미 정렬이 되어 있으므로 먼저 하나씩 빼서 다시 링크드 리스트로 만들자.
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// 마지막 원소
if (list1.next == null) {
ListNode node = new ListNode(list1.val);
return node;
}
if (list2.next == null) {
ListNode node = new ListNode(list2.val);
return node;
}
System.out.println(list1.val);
System.out.println(list1.next);
// 결과:
// 1
// ListNode@49c2faae
// 처음 값부터 순서대로 들어오는 듯
if (list1.val <= list2.val) {
ListNode node1 = new ListNode(list1.val);
ListNode node2 = new ListNode(list2.val);
node1.next = node2;
// return node1;
return mergeTwoLists(node1, node2);
}
ListNode node1 = new ListNode(list2.val);
ListNode node2 = new ListNode(list1.val);
node1.next = node2;
// return node1;
return mergeTwoLists(node1, node2);
}
}먼가 해결이 될 것 같지만 안 되네요. 솔루션에서 재귀를 사용했던 것을 얼핏 봤고 list가 빈 경우에 대해 바로 return을 해준 것을 봐서 그건 사용했습니다.
일단 LinkedList를 자료구조를 공부하면서 개념만 봤지 실제로 이렇게 구현한 것은 처음봤습니다. 조건을 보니 배열처럼 되어 있어서 배열처럼 인덱스로 접근을 했는데 바로 오류가 뜨더라고요.
일단 Type이 ListNode인 것을 떠올리고 인스턴스의 속성으로 접근을 해 보니 결과가 아래 사진처럼 나왔습니다.
링크드 리스트의 노드가 데이터와 포인터로 연결되어 있다는데 그것을 디버깅으로 확인해 본 순간입니다... 감격스럽네요!
이것을 확인하고나니 어떤식으로 접근해야 하는지 나름 감이 왔습니다.
if (list1.val <= list2.val) {
ListNode node1 = new ListNode(list1.val);
ListNode node2 = new ListNode(list2.val);
node1.next = node2;
return node1;
} else {
ListNode node1 = new ListNode(list2.val);
ListNode node2 = new ListNode(list1.val);
node1.next = node2;
return node1;
}매개변수로 들어온 값들의 value를 비교하여 ListNode의 인스턴스를 만들어서 노드를 연결시켜 줬습니다.
이렇게 return을 하니 [1,1]이 나오더라고요. 그래서 재귀를 쓰는구나를 깨달았습니다. 그래서 재귀를 사용해 봤지만 풀리지는 않네요.
1시간 이상을 고민하고 시도를 해 봤지만 방법을 모르겠습니다. 노드를 연결 후 그 다음 노드를 연결한 노드에 어떻게 연결할지 링크드 리스트가 익숙하지 않아서 잘 모르겠네요.
여러 번 시도한 후 이제는 솔루션을 봐도 이해가 되겠다 싶어서 솔루션을 봤습니다. 좀 허무한 감도 있지만 시원하고 확실히 고민을 하고 풀려고 노력한 보람이 있네요. 처음보다는 확실히 이해가 잘 됩니다.
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}전 마지막 노드의 포인터가 null일 때가 종료조건인줄 알았는데 그려서 확인해보니 마지막 재귀 호출때 list에 null이 할당되어서 이게 종료 조건이구나 하고 생각했습니다.
하지만, 정확히 어떤 플로우인지 잘 몰라서 그려서 확인해 봤는데도 잘 모르겠습니다. 노드라는 구조가 어떻게 앞뒤로 연결되는지 직관적으로 받아들여지지가 않네요. 디버깅으로 어떻게 재귀를 통해 노드들이 연결되나 확인해 봐야겠습니다.
피보나치처럼 재귀 방식을 확인하려고 했으나 노드가 앞뒤로 어떻게 연결되는지 파악이 쉽지가 않습니다.
