문제 정의

• 두 리스트를 입력받아 하나의 리스트를 반환하는 함수를 구현한다.
• 두 리스트는 정렬된 정수들로 이루어져 있으며, 인자의 개수는 서로 다를수도 있다.
• 두 리스트의 인자들 모두로 이루어진 리스트를 반환하되, 반환되는 리스트 역시 정렬되어 있어야 한다.

<예시1>

Input: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

<예시2>

Input: list1 = [], list2 = []

Output: []

<예시2>

Input: list1 = [], list2 = [0]

Output: [0]

풀이

• 각 리스트의 노드의 값을 비교해가며, 작은 값에서 큰 값으로 링크를 이어나가는 방법으로 문제를 해결한다.

class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

	/* 두 리스트가 모두 공백이라면, null을 반환한다 */
        if((list1 == null)&&(list2 == null))
            return null;
		
	/* 한 리스트가 공백이면, 다른 리스트를 반환한다. */        
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;

        ListNode cur1 = list1;	// list1을 순회할 노드 포인터이다.
        ListNode cur2 = list2;	// list2을 순회할 노드 포인터이다.

        ListNode cur = null;	// 두 리스트를 연결한 리스트를 이을 노드 포인터이다.
        ListNode head = null;	// 연결한 리스트의 헤드 노드 포인터이다.

	// 첫 노드를 결정하여 헤드 노드 포인터를 지정한다.
        if(cur1.val >= cur2.val)
        {
            head = list2;
            cur = cur2;
            cur2 = cur2.next;
        }
        else
        {
            head = list1;
            cur = cur1;
            cur1 = cur1.next;
        }

	// 한 리스트라도 null이 되면 비교 반복을 종료한다.
        while((cur1!=null)&&(cur2!=null))
        {
    	    if(cur1.val >= cur2.val)	// 비교하여, 연결한다
            {
                cur.next = cur2;
                cur = cur2;
                cur2 = cur2.next;
            }
            else			// 비교하여 연결한다.
            {
                cur.next = cur1;
                cur = cur1;
                cur1 = cur1.next;
            }
        }

	// list2이 작아서 null이 되어버렸다면, cur 노드에 남은 cur1 노드를 연결한다.
        if(cur1 != null)
            cur.next = cur1;
            
	// list1이 작아서 null이 되어버렸다면, cur 노드에 남은 cur2 노드를 연결한다.
        if(cur2 != null)
            cur.next = cur2;

        return head;

    }
}