시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
두 숫자 더하기 비어 있지 않은 두 개의 연결 목록 음이 아닌 정수를 나타냅니다. 숫자는 역순으로 저장되며 모든 노드는 단일 숫자 만 포함해야합니다. 두 숫자를 더하고 연결 목록을 사용하여 결과를 인쇄합니다.
차례
입력 형식
두 개의 정수 값 N1 및 N2를 포함하는 첫 번째 줄. 첫 번째 숫자의 N1 자리를 포함하는 두 번째 줄. 번호의 N2 자리를 포함하는 세 번째 줄입니다.
출력 형식
연결 목록을 사용하여 결과를 인쇄합니다.
제약
- 0 <= 노드 값 <= 9.
Example Input-1: 3 3 5 2 1 2 8 5
Example Output-1: 7 0 7
두 숫자 추가에 대한 설명
첫 번째 숫자는 125이고 두 번째 숫자는 582입니다. 더하면 707이 나옵니다. 따라서 최종 답은 707입니다. 더 나은 이해를 위해 아래 이미지를 참조하십시오.
단계 : 1 주어진 입력 형식에 따라 연결 목록을 만듭니다. 연결 목록의 숫자를 역순으로 추가합니다.
단계 : 2 각 연결 목록에서 한 자리 씩 오른쪽에서 왼쪽으로 이동합니다. 오른쪽에서 왼쪽으로 이동하기 위해 이러한 연결 목록을 뒤집습니다. 두 연결 목록의 노드 데이터를 추가하고 다른 연결 목록에 저장합니다. 추가 사이에 캐리가 발생하면 다음 노드에서 사용하십시오.
단계 : 3 머리를 하나씩 이동하고 결과 연결 목록에 값을 추가합니다.
단계 : 4 머리를 하나씩 이동하고 결과 연결 목록에 값을 추가합니다.
단계 : 5 이제 결과 연결 목록 7-> 0-> 7의 값을 인쇄합니다.
두 숫자 더하기 알고리즘
Algorithm:
Step:1 If h1 is the head of first linked list and h2 is the head of second linked list then:
while(h1!=NULL and h2!=NULL) then:
1.1) add the data of both nodes and add to a final resultant linked list.
Step:2 while(h1!=NULL) then:
add the nodes of linked list 1 to the resultant linked list.
Step:3 while(h2!=NULL) then:
add the nodes of linked list 2 to the resultant linked list.
Step:4 Print the final resultant linked list.
두 숫자 추가 구현
/*C++ Implementation of Add two numbers problem*/
#include<bits/stdc++.h>
using namespace std;
/*structure of node of linked list which contain data and a pointer which is point to the next node*/
struct ListNode
{
/*value of node*/
int val;
/*pointer to the next node*/
ListNode *next;
};
/*Create a node with given data*/
ListNode *newnode(int data)
{
ListNode *temp= new ListNode();
temp->val=data;
temp->next=NULL;
return temp;
}
void create_linked_list(ListNode** head, int data)
{
/*allocate node*/
ListNode* temp = newnode(data);
/*link the old list off the new node*/
temp->next=(*head);
/* move the head to point to the new node*/
(*head)=temp;
}
void print_linked_list(ListNode* head)
{
while(head!=NULL)
{
cout<<head->val<<" ";
head=head->next;
}
}
/*add two linked list*/
ListNode* add_two_numbers(ListNode* l1, ListNode* l2)
{
int carry=0;
ListNode* res;
ListNode **ans=&res;
/*if both linked list have nodes*/
while(l1!=NULL&&l2!=NULL)
{
(*ans)= newnode((l1->val+l2->val+carry)%10);
carry=(l1->val+l2->val+carry)/10;
ans=&((*ans)->next);
l1=l1->next;
l2=l2->next;
}
/*if linked list 1 have nodes*/
while(l1!=NULL)
{
(*ans)= newnode((l1->val+carry)%10);
carry=(l1->val+carry)/10;
ans=&((*ans)->next);
l1=l1->next;
}
/*if linked list 2 have nodes*/
while(l2!=NULL)
{
(*ans)= newnode((l2->val+carry)%10);
carry=(l2->val+carry)/10;
ans=&((*ans)->next);
l2=l2->next;
}
/*if their is generate a carry then create one more node in linked list and store the carry.*/
if(carry>0)
{
(*ans)= newnode(carry);
carry/=10;
ans=&((*ans)->next);
}
return res;
}
/*function use to reverse the linked list*/
ListNode* reverse_linked_list(ListNode* head)
{
ListNode* current=head;
ListNode* next=NULL;
ListNode* prev=NULL;
while(current!=NULL)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
return prev;
}
int main()
{
int n1,n2;
/*take the input n1,n2*/
cin>>n1>>n2;
ListNode* result=NULL;
ListNode* ll1=NULL;
ListNode* ll2=NULL;
/*take input linked list 1*/
for(int i=0;i<n1;i++)
{
int x;
cin>>x;
create_linked_list(&ll1,x);
}
/*take input linked list 2*/
for(int i=0;i<n2;i++)
{
int x;
cin>>x;
create_linked_list(&ll2,x);
}
/*print first linked list*/
cout<<"First linked list is: ";
print_linked_list(ll1);
cout<<endl;
/*print second linked list*/
cout<<"Second linked list is: ";
print_linked_list(ll2);
cout<<endl;
/*reverse linkel list 1*/
ListNode* l1=reverse_linked_list(ll1);
/*reverse linkel list 2*/
ListNode* l2=reverse_linked_list(ll2);
ListNode* ans= add_two_numbers(l1,l2);
/*print reslutant linked list*/
cout<<"Resultant linked list is: ";
print_linked_list(ans);
cout<<endl;
return 0;
}
3 2 2 4 3 5 6
First linked list is: 3 4 2 Second linked list is: 6 5 Resultant linked list is: 7 0 4
시간 복잡성
의 위에) 여기서 N은 n1, n2의 최대 값입니다. 연결 목록을 탐색합니다. 선형 시간 따라서 시간 복잡성도 선형입니다.
공간 복잡성
의 위에) N 노드를 포함 할 수있는 또 다른 연결 목록을 생성하기 때문입니다. 여기서 N은 큰 크기 연결 목록의 숫자입니다.
