[ Top Interview 150 ] 21. Merge Two Sorted Lists

문제

21. Merge Two Sorted Lists

 You are given the heads of two sorted linked lists list1 and list2.

 Merge the two lists into 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.

• Input : 오름차순으로 정렬된 singly-linked list 2개의 head node (list1, list2)
• Output : list1, list2의 node들을 하나의 linked list로 정렬하고 head node를 반환

알고리즘 전략

• list1, list2가 모두 null에 도달할 때까지 반복

  • list1, list2 중 작은 node를 선택
  • 해당 node를 이전 node에 붙임
  • 해당 node의 list는 다음으로 넘김

• 주의 사항

  • null이 자주 등장할 수 있으므로 NullPointerException에 주의하자

작성 답안

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        ListNode head = getSmaller(list1, list2);

        if (head == null) { // list1, list2 둘 다 null 인 경우
            return null;
        }

        if (head == list1) {
            list1 = list1.next;
        } else {
            list2 = list2.next;
        }

        ListNode current = head;
        while (list1 != null || list2 != null) {
            ListNode smallNode = getSmaller(list1, list2);
            current.next = smallNode;
            current = smallNode;

            if (current == list1) {
                list1 = list1.next;
            } else {
                list2 = list2.next;
            }
        }

        return head;
    }

    private ListNode getSmaller(ListNode node1, ListNode node2) {
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }

        return node1.val <= node2.val ? node1 : node2;
    }
}

/**
 * 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; }
 * }
 */

다른 답안 찾아보기

• 재귀를 이용한 답안
  • 전략 : 각 함수마다 작은 노드 하나만을 뽑아내고 나머지는 같은 함수를 호출하여 처리함
  • 해당 문제가 재귀가 적절한 이유 : array 같은 경우에는 subArray를 생성해서 함수를 호출하므로 중간 array들이 많이 만들어지는데, 위 문제는 ListNode를 사용하기 때문에 따로 중간 객체를 생성하지 않는다.
  • 메모리, 시간 비교 : stack 영역에 함수가 계속 쌓이기 때문에 메모리 사용량은 이전보다 증가됨

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
        if (list1 == null) {return list2;}
        return list1;
    }
}