[Linked List] Merge Two Sorted Lists

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.

 

Linked List 문제에서 항상 기억할 점은

 

1) 첫 input은 Head Node이다

2) 우리가 받는 input은 Head Node와 Tail Node(next 메소드로 얻어낼 수 있는) 뿐이다

3) 따라서 유연한 조작을 위해 index가 필요하다

 

라는 부분이다

 

내 풀이는 다음과 같다

 

이를 도식화시키면 다음과 같은데 차근차근 설명해보면

 

결과값이 될 List를 만들고, 그 List의 객체를 만든다.

얘가 인덱스 노드가 된다.

우리는 인덱스 노드에 적절하게 input List들의 원소를 배치할 것이다.

 

첫 Loop에서 Change에는 아무것도 없을 것이다.

따라서 가상의 노드 A 라고 생각해보자.

우리는 Change노드의 다음부터 merge된 List를 만들어 주면 된다.

일단 두개의 인풋 중 더 작은 값인 l1을 if의 input으로 받는다.

change의 tail node에 l1을 배치한다.

 

여기까지 실행하면 mergedList는 [ A, l1 ]으로 나타날 것이다.

 

 

이제 l1의 다음 input을 next 메소드를 이용하여 l1 List input의 tail node로 바꾸자

l1이 [1, 2, 4]로 입력되었다면, 첫 input인 1에 대한 처리가 끝났으므로 l1에 2를 배치하는 것이다

else문에 있는 l2에 대한 처리도 동일하다

 

이렇게 바꾸고 나면 change의 head노드 역시 change.next를 이용하여 현재 tail node로 변경한다

 

여기까지 루프가 끝나면 merged List는 [ A, 1, 1, 2, 2, 3, 4] 가 될 것이다

 

예시의 경우에는 바로 리턴 구문을 작성하면 되는데

문제는 l1과 l2의 병합이 한쪽 list 원소가 남은채로 끝나는 경우이다.

예를 들어 l1 [1,2,4]와 l2 [2,3,5,6,7,8]이 들어왔다고 해보자

l1은 4가 처리되면 null이 되므로 Loop가 끝이 난다.

그러나 l2의 5,6,7,8은 처리되지 않았다.

 

이런 경우에는 next에 5만 붙여주면된다.

남은 값들은 분명 처리된 값들보다 클 것이기 때문이다.

따라서 null이 아닌 List에 대해 첫 원소만 change의 tail node로 지정해준다

 

마지막으로 정답을 리턴하는데 여기서도 조심해야 한다

우리가 가상의 노드 A를 만들었기 때문이다

예시가 여기까지 진행되면 merged List는 [ A, 1, 1, 2, 2, 3, 4]가 될텐데, 

여기서 A는 제외해야 한다.

따라서 next를 리턴시킨다