시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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은 큰 크기 연결 목록의 숫자입니다.
