21. 두 개의 정렬된 리스트 병합하기

이 문제는 두 개의 정렬된 연결 리스트를 하나의 정렬된 연결 리스트로 병합하는 것입니다. 주어진 두 리스트를 하나의 리스트로 합치면서도 정렬 상태를 유지해야 합니다. 이 문제를 해결하기 위해 우리는 다음과 같은 방법을 사용할 수 있습니다.

알고리즘의 핵심 아이디어

두 개의 정렬된 리스트를 병합하기 위해, 두 리스트의 현재 노드 값을 비교하여 더 작은 값을 결과 리스트에 추가합니다. 이 과정을 반복하여 두 리스트를 모두 순회한 후, 남아있는 노드들을 결과 리스트에 추가합니다. 이렇게 하면 결과 리스트도 자연스럽게 정렬된 상태를 유지하게 됩니다.

코드의 주요 로직 설명

1. 더미 노드 생성: 결과 리스트의 시작을 쉽게 관리하기 위해 더미 노드를 생성합니다. 이 노드는 실제 결과 리스트에 포함되지 않지만, 결과 리스트의 시작점을 쉽게 추적할 수 있도록 도와줍니다.

2. 현재 노드 포인터: current라는 포인터를 사용하여 결과 리스트의 마지막 노드를 가리킵니다. 처음에는 더미 노드를 가리키고, 이후에는 결과 리스트의 마지막 노드를 가리키도록 업데이트합니다.

3. 리스트 병합 반복문: 두 리스트의 노드를 순회하면서, 각 리스트의 현재 노드 값을 비교합니다. 더 작은 값을 가진 노드를 결과 리스트에 추가하고, 해당 리스트의 포인터를 다음 노드로 이동합니다.

4. 남은 노드 처리: 한 리스트가 끝났을 때, 다른 리스트에 남아있는 노드들을 결과 리스트에 추가합니다. 두 리스트 중 하나는 반드시 끝나기 때문에, 남아있는 노드는 최대 하나의 리스트에만 존재합니다.

각 단계별 동작 과정

• 초기화: 더미 노드를 생성하고 current 포인터를 더미 노드로 설정합니다.
• 반복문: list1과 list2가 모두 null이 아닐 때까지 반복합니다.
  • list1.val과 list2.val을 비교하여 더 작은 값을 가진 노드를 current.next에 연결합니다.
  • current 포인터를 다음 노드로 이동합니다.
  • 작은 값을 가진 리스트의 포인터를 다음 노드로 이동합니다.
• 남은 노드 연결: 반복문이 끝난 후, list1이나 list2 중 하나는 null이 아닐 수 있습니다. 이 경우 남아있는 노드들을 current.next에 연결합니다.
• 결과 반환: 더미 노드의 다음 노드(dummy.next)를 반환합니다. 이 노드가 실제 병합된 리스트의 시작 노드입니다.

핵심 변수들의 역할

• dummy: 결과 리스트의 시작을 쉽게 추적하기 위한 임시 노드입니다.
• current: 결과 리스트의 마지막 노드를 가리키며, 새로운 노드를 추가할 때 사용됩니다.
• list1, list2: 각각의 리스트에서 현재 비교할 노드를 가리킵니다.

왜 이 방법이 효과적인지

이 방법은 두 리스트를 동시에 순회하면서 각 단계에서 최소값을 선택하여 결과 리스트에 추가하기 때문에, 전체 리스트가 정렬된 상태를 유지합니다. 더미 노드를 사용함으로써 결과 리스트의 시작을 쉽게 추적할 수 있으며, 코드가 간결하고 이해하기 쉽습니다. 또한, 이 알고리즘은 각 리스트를 한 번씩만 순회하므로 시간 복잡도가 O(n + m)으로 매우 효율적입니다. 여기서 n과 m은 각각 두 리스트의 길이입니다.