두 숫자 더하기

난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 쿠팡 DocuSign의 Facebook 구글 Microsoft 동네 짱 VM웨어 월마트 연구소 Yahoo
연결된 목록 수학조회수 69

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

참조

균열 시스템 설계 인터뷰
Translate »