기술면접 알고리즘 [Linked List] : 링크드 리스트 덧셈 (Add two numbers represented by linked lists)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

 

링크드 리스트 덧셈 (Add two numbers represented by linked lists)

링크드 리스트로 숫자가 주어졌을 때, 두 리스트를 더해 다음과 같은 리스트를 리턴하는 함수를 구현해 보자.

해당 함수는 재귀적으로 구현할 수도 있고, stack 을 이용해 구현할 수도 있다. 

혹은, 링크드 리스트를 reverse 시킨 후, loop 을 돌려 덧셈을 해도 같은 결과를 구할 수 있다. 아래 코드는 링크드 리스트를 역전시킨 방식을 구현한 코드이다.

#include <stdio.h>
#include <memory>
#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(char data) : data{data}, next{nullptr} {}
};

struct List {
    List() : head{nullptr} {}
    
    void insert(int x) {
        Node* newNode = new Node(x);
        
        if (!head) {
            head = std::move(newNode);
            return;
        }

        newNode->next = head;
        head = newNode;        
    }
    
    int compare(List& a) {

        Node* left = this->head;
        Node* right = a.head;

        while (left && right) {

            if (left->data > right->data)
                return 1;
            else if (right->data > left->data)
                return -1;
            else {
                left = left->next;
                right = right->next;
            }

        }

        // if length are same
        if (!left && !right) {
            return 0;
        } else if (!left) {
            return -1;
        } else return 1;
    }

    friend std::ostream& operator<<(std::ostream &os, const List &list);
    friend List add(List& a, List& b);
    
private:
    Node* head;
};

std::ostream& operator<<(std::ostream &os, const List &list) {
    Node* temp = list.head;

    if (!temp) {
        std::cout << "Linked list is empty" << std::endl;
        return os;
    }
    
    while (temp) {
        os << temp->data << " ";
        temp = temp->next;
    }
    os << std::endl;
    
    return os;
}

List _add(Node* a, Node* b) {

	List result;

	Node* l = a;
	Node* r = b;
	int added = 0;
	int carry = 0;

	while (l && r) {
		added = l->data + r->data + carry;
		
		carry = added / 10;
		result.insert(added % 10);

		l = l->next;
		r = r->next;
	}

	if (!l && !r && carry > 0) {
		result.insert(carry);
	}
	else if (l && !r) {
		while (l) {
			added = l->data + carry;
			carry = added / 10;
			result.insert(added % 10);

			l = l->next;
		}
	}
	else {
		while (r) {
			added = r->data + carry;
			carry = added / 10;
			result.insert(added % 10);

			r = r->next;
		}
	}

	return result;
}

List add(List& a, List& b) {

	List rev_a;
	Node* temp = a.head;
	while (temp) {
		rev_a.insert(temp->data);
		temp = temp->next;
	}

	List rev_b;
	temp = b.head;
	while (temp) {
		rev_b.insert(temp->data);
		temp = temp->next;
	}

	return _add(rev_a.head, rev_b.head);
}

int main()
{
    List l;
    
    l.insert(3);
    l.insert(6);
    l.insert(5);

    // std::cout << l;


    List r;

    r.insert(2);
    r.insert(4);
    r.insert(8);
    
    List output = add(l, r);

    std::cout << output << std::endl;

    
    return 0;
}