[자바 알고리즘 인터뷰] 8장 연결 리스트(2) - 두 정렬 리스트의 병합

https://leetcode.com/problems/merge-two-sorted-lists/description/

 

- 정렬되어 있는 두 연결 리스트를 합쳐라 

 

 

풀이 1) 재귀 구조로 연결 

 

- 병합 정렬에서 마지막 조합시 첫 번째 값부터 차례대로 비교하면 한 번에 해결되듯이, 이 또한 병합 정렬의 마지막 조합과 동일한 방식으로 첫 번째부터 비교하면서 리턴

 

- 먼저 list1과 list2의 값을 비교하여 작은 값이 있는 쪽을 재귀 호출로 엮은 다음 결과를 리턴 

- 재귀 호출시 엮는 쪽은 그 다음 노드를 입력값으로 전달 

- 어느 한쪽이 널(Null)이 된다면 널이 아닌 노드를 리턴하면서 마무리

출처: 자바 알고리즘 인터뷰 with  코틀린 저자:박상길 <책만>

 

 

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //두 노드 중 한쪽이 널이면 널이 아닌 노드를 리턴
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        //l2가 더 크면 l1에 재귀 호출 결과를 엮고 l1를 리턴
        if(list1.val < list2.val)
        {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else
        {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

1밀리초