시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
연결된 목록 선형 속성에서 배열과 매우 유사합니다. 두 개의 정렬 된 배열을 병합하여 전체적으로 정렬 된 배열을 형성 할 수 있습니다. 이 문제에서는 정렬 된 두 개의 연결 목록을 병합해야합니다. 그 자리에 정렬 된 방식으로 두 목록의 요소를 포함하는 새 목록을 반환합니다.
차례
예
L1 = 1 -> 2 -> 9 L2 = 1 -> 3 -> 4
1 1 2 3 4 9
접근
이를 수행하는 가장 간단한 방법은 두 포인터 기술. 비어있는 새 목록을 만듭니다. 두 포인터 사이에 더 작은 요소를 추가하고 해당 포인터를 증가시킵니다. 이것은 좋은 접근 방식이지만 공간을 소비하는 추가 목록을 만들어야합니다.
최적의 접근 방식은 작업을 수행하기 위해서만 일정한 공간을 소비해야합니다. 그 자리에서 정렬. 반복적 인 접근 방식을 따를 수 있습니다. 두 목록에 이미 노드가 저장되어 있습니다. 새 목록 포인터와 후속 "다음 포인터”는 메모리의 미리 정의 된 노드를 가리켜 야합니다. 이 과정에서 우리는 아니 새 노드.
알고리즘 (순진한 접근 방식)
- 함수 만들기 mergeTwoSortedLists () 두 개의 목록 포인터를 인수로 사용합니다.
- 목록 중 하나가 Null 다른 하나 돌려줘
- 만들기 임시직 두 목록의 헤드 중 더 작은 노드를 가리키는 변수
- 이제 적어도 하나의 노드가 결과에 추가되므로 하나의 헤드가 증가해야합니다.
- 이것은 하위 문제를 만듭니다. 따라서 동일한 재귀 함수를 호출하고 temp에 추가하십시오.
- List1.value <List2.value 인 경우
- 온도 = 새로운 ListNode (List1.value) , 임시-> 다음 = mergeTwoSortedLists (List1-> next, List2)
- List2.value <= List1.value 인 경우
- 온도 = 새로운 ListNode (List2.value) , 임시-> 다음 = mergeTwoSortedLists (List1, List2-> next)
- 반품 임시직 원하는 목록을 얻으려면
알고리즘 (최적)
- 호출 될 새 목록 포인터를 만듭니다. dummy_head.
- 유지 "프리 헤드”(포인터 복사) 목록에 액세스 할 수 있도록 머리 주소.
- "다음 포인터”of dummy_head는 목록에서 미리 정의 된 노드를 가리 키도록 조작해야합니다. l1 및 l2.
- 위의 작업을 다음과 같은 방법으로 수행 할 수 있습니다.
- 머리에서 시작하는 포인터로 목록을 계속 반복하십시오.
- 목록 중 하나가 완전히 순회되지 않는 한 :
- 두 개의 목록 포인터에서 더 작은 값의 노드를 dummy_head, 해당 포인터를 증가시킵니다.
- 이제 포인터 중 적어도 하나는 없는. 따라서 널이 아닌 더미 머리에 목록.
- 반환 머리 더미 목록의.
실시
두 개의 정렬 된 목록을 병합하는 C ++ 프로그램
순진한 접근
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
if(!l1)
return l2;
if(!l2)
return l1;
listNode* temp;
if(l1->value < l2->value)
{
temp = new listNode(l1->value);
temp->next = mergeTwoSortedLists(l1->next , l2);
}
else
{
temp = new listNode(l2->value);
temp->next = mergeTwoSortedLists(l1 , l2->next);
}
return temp;
}
void print(listNode* head)
{
while(head)
{
cout << head->value << " ";
head = head->next;
}
cout << '\n';
return;
}
int main()
{
listNode* l1 = new listNode(1);
l1->next = new listNode(2);
l1->next->next = new listNode(9);
listNode* l2 = new listNode(1);
l2->next = new listNode(3);
l2->next->next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
return 0;
}
최적의 방법
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
while(l1 && l2)
{
if(l1->value < l2->value)
{
dummy_head->next = l1;
l1 = l1->next;
}
else
{
dummy_head->next = l2;
l2 = l2->next;
}
dummy_head = dummy_head->next;
}
dummy_head->next = (l1 ? l1 : l2);
return prehead->next;
}
void print(listNode* head)
{
while(head)
{
cout << head->value << " ";
head = head->next;
}
cout << '\n';
return;
}
int main()
{
listNode* l1 = new listNode(1);
l1->next = new listNode(2);
l1->next->next = new listNode(9);
listNode* l2 = new listNode(1);
l2->next = new listNode(3);
l2->next->next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
return 0;
}
1 1 2 3 4 9
두 개의 정렬 된 목록을 병합하는 Java 프로그램
순진한 접근
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class merge_two_sorted_lists
{
public static void print(listNode head)
{
while(head != null)
{
System.out.print(head.value + " ");
head = head.next;
}
return;
}
public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
{
if(l1 == null)
return l2;
if(l2 == null)
return l1;
listNode temp;
if(l1.value < l2.value)
{
temp = new listNode(l1.value);
temp.next = mergeTwoSortedLists(l1.next , l2);
}
else
{
temp = new listNode(l2.value);
temp.next = mergeTwoSortedLists(l1 , l2.next);
}
return temp;
}
public static void main(String args[])
{
listNode l1 = new listNode(1);
l1.next = new listNode(2);
l1.next.next = new listNode(9);
listNode l2 = new listNode(1);
l2.next = new listNode(3);
l2.next.next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
}
}
최적의 방법
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class merge_two_sorted_lists
{
public static void print(listNode head)
{
while(head != null)
{
System.out.print(head.value + " ");
head = head.next;
}
return;
}
public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
{
listNode dummy_head = new listNode(-1) , prehead = dummy_head;
while(l1 != null && l2 != null)
{
if(l1.value < l2.value)
{
dummy_head.next = l1;
l1 = l1.next;
}
else
{
dummy_head.next = l2;
l2 = l2.next;
}
dummy_head = dummy_head.next;
}
dummy_head.next = ((l1 != null) ? l1 : l2);
return prehead.next;
}
public static void main(String args[])
{
listNode l1 = new listNode(1);
l1.next = new listNode(2);
l1.next.next = new listNode(9);
listNode l2 = new listNode(1);
l2.next = new listNode(3);
l2.next.next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
}
}
1 1 2 3 4 9
복잡성 분석
시간 복잡성 정렬 된 두 목록을 병합하는 방법
O (N + M), 어디에 N 및 M 두 목록의 길이입니다. 두 가지 접근 방식 모두에서 두 목록을 모두 한 번 탐색하므로 두 알고리즘 모두 선형입니다.
공간 복잡성 정렬 된 두 목록을 병합하는 방법
최적의 접근 방식에서는 포인터 조작. 따라서 변수의 상수 공간은 메모리 사용량을 설명합니다. 따라서 최적의 방법은 다음과 같은 공간 복잡성을 갖습니다. O (1). O (N + M) 공간은 논의 된 순진한 접근법에 사용됩니다.
