mergeTwoLinkedLists

두 개의 오름차순으로 정렬된 단일 연결 리스트가 주어졌을 때, 이 두 리스트를 병합하는 것입니다. 병합된 리스트도 오름차순으로 정렬되어야 합니다. 즉, 첫 번째 두 리스트의 노드를 연결하여 새로운 단일 연결 리스트를 만들어야 합니다.

이 문제를 풀기 위해서는 O(l1.length + l2.length) 시간 복잡도를 가져야 합니다. 이것이 면접에서 요구되는 작업입니다.

예를 들어, 다음과 같은 두 개의 연결 리스트가 주어졌다고 가정해 봅시다:

리스트 1: 1 -> 3 -> 5
리스트 2: 2 -> 4 -> 6
이 두 리스트를 병합하면 다음과 같은 결과가 나와야 합니다:

병합된 리스트: 1 -> 2 -> 3 -> 4 -> 5 -> 6
이 문제를 풀기 위해서는 두 리스트를 순회하면서 노드를 비교하고 새로운 연결 리스트를 만들어야 합니다. 코드로 구현할 때 주의해야 할 점은, 두 리스트 중 하나가 끝날 때까지 계속해서 노드를 추가해야 한다는 것입니다.

// Singly-linked lists are already defined with this interface:
// class ListNode<T> {
//   public T value { get; set; }
//   public ListNode<T> next { get; set; }
// }
ListNode<int> solution(ListNode<int> l1, ListNode<int> l2) {
    ListNode<int> head1 = l1;
    ListNode<int> head2 = l2;
    ListNode<int> dummyHead = new ListNode<int>();
    ListNode<int> current = dummyHead;
    
    while (head1 != null && head2 != null) {
        if (head1.value < head2.value) {
            current.next = head1; // 이미 있는 노드를 사용
            head1 = head1.next;
        } else {
            current.next = head2; // 이미 있는 노드를 사용
            head2 = head2.next;
        }
        current = current.next;
    }
    
    // 남은 노드 추가
    while (head1 != null) {
        current.next = head1;
        current = current.next;
        head1 = head1.next;
    }
    
    while (head2 != null) {
        current.next = head2;
        current = current.next;
        head2 = head2.next;
    }
    
    return dummyHead.next;
}

새로운 노드를 생성해서 해야하는 줄 알았는데, 이미 있는 노드를 연결해서 사용하면 되었습니다. 더 간단하고 공간복잡도를 줄여주었습니다.