46. Permutations (두 개의 정렬된 리스트 병합)

정렬된 두 링크 리스트 list1과 list2의 헤드가 주어집니다.
두 개의 리스트 을 하나의 정렬된 리스트로 병합합니다. 리스트는 처음 두 리스트의 노드를 서로 연결하여 만들어야 합니다.
병합된 링크 리스트의 헤드 부분을 반환합니다.

 

예시 1:

입력: list1 = [1,2,4], list2 = [1,3,4]
출력: [1,1,2,3,4,4]

 

예시 2:

입력: list1 = [], list2 = []
출력: []

 

예시 3:

입력: list1 = [], list2 = [0]
출력: [0]

 

조건:

• 두 목록의 노드 수는 [0, 50] 범위입니다.
• -100 <= Node.val <= 100
• list1과 list2는 모두 비내림차순으로 정렬됩니다.

 

정답:

public class Solution 
{
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) 
    {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode resultNode = new ListNode();
        ListNode nextHeadNode = resultNode;

        while (list1 != null && list2 != null) 
        {
            ListNode tmpNode;
            if (list1.val <= list2.val) 
            {
                tmpNode = new ListNode(list1.val);
                list1 = list1.next;
            } 
            else 
            {
                tmpNode = new ListNode(list2.val);
                list2 = list2.next;
            }
            nextHeadNode.next = tmpNode;
            nextHeadNode = nextHeadNode.next;
        }

        if(list1 == null) 
            nextHeadNode.next = list2;
        else if(list2 == null) 
            nextHeadNode.next = list1;

        return resultNode.next;
    }
}

해설: 이미 두 리스트는 오름차순으로 정렬이 되있으므로 한 리스트가 빌때까지 val과 비교를 반복합니다.

그리고 더 적은 수라면 tmpNode에 추가한 후 nextHeadNode의 next에 넣은 이후 nextHead = nextHeadNode.next 코드로 다음 head를 맞춰줍니다.

반복이 끝났다면 남은 리스트는 이미 정렬이 되어있으므로 그대로 붙여줍니다.

그리고 마지막으로 nextHeadNode의 가장 첫부분의 헤드인 resultNode.next를 return해줍니다.