2 개의 정렬되지 않은 링크 된 목록을 하나의 정렬 된 링크 된 목록에 병합

Question

2 개의 정렬되지 않은 링크 된 목록을 하나의 정렬 된 연결된 목록으로 효율적으로 병합하기 위해 문제를 해결하려고합니다. 나는 몇 가지 아이디어가 있습니다.

1. 은 단순히이 링크 된 목록을 병합하고
2. 정렬 개별적 및 병합 정렬 (머지 소트 또는 퀵)보다 두 사람은이 개념을 따릅니다.

How to merge two sorted arrays into a sorted array?

사람들은 내가 생각할 수에 대한 모든 알고리즘이다. 다른 사람들이이 문제를 해결하기 위해 더 효과적이고 효율적인 방법을 가지고 있습니까?

Answer 1

두 목록을 단일 목록으로 연결하고 해당 목록을 정렬해야합니다.

처음 정렬하는 것보다 훨씬 간단하며 코드가 적고 두 번째 옵션과 동일한 시간이 소요됩니다.

Answer 2

먼저 두 목록을 병합하여 하나의 연결된 목록을 만든 다음이 단일 목록을 정렬하십시오.

Answer 3

또 다른 방법은 BST를 사용하는 것입니다. BST에 목록 1 요소를 추가 한 다음 BST에 목록 2 요소를 추가하십시오. 그런 다음 BST의 inorder 탐색을 사용하고 요소가 정렬 될 목록 3에 놓입니다.

O이 그들을 병합 후 두 목록에 머지 소트를하고 유사한 성능을 제공 할