[코딩인터뷰 완전정복] 2.5 리스트의 합

Q : 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 첫 번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자 두개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라.

// LinkedList.h
#include <iostream>

struct node {
	int data;
	node *next;
};

class linked_list {
private:
	node *head, *tail;
public:
	linked_list() {
		head = NULL;
		tail = NULL;
	}

	node* add_node(int n) {
		node *temp = new node;
		temp->data = n;
		temp->next = NULL;
		if (head == NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = tail->next;
		}

		return temp;
	}

	void addFirst(int x) {
		node *temp = new node();
		temp->data = x;
		temp->next = head;
		head = temp;
		if (tail == NULL) tail = temp;

	}

	void addFirst(node *node) {
		node->next = head;
		head = node;
		if (tail == NULL) tail = node;

	}

	int removeFirst() {
		if(head == NULL) return NULL;

		int data = head->data;
		head = head->next;

		return data;
	}

	node* first() {
		return head;
	}

	void printLinkedList() {
		if (head == NULL) return;

		node* currentNode = head;
		while (currentNode->next != NULL) {
			printf("%d - ", currentNode->data);
			currentNode = currentNode->next;
		}
		printf("%d", currentNode->data);

		printf("\n");
	}
};

#include <iostream>
#include "LinkedList.h"

linked_list SumTwoList(linked_list list1, linked_list list2) {
	node *num1, *num2;
	num1 = list1.first();
	num2 = list2.first();

	linked_list sumList;
	int sum;
	int carry = 0;

	while(num1 != NULL && num2 != NULL) {
		sum = num1->data + num2->data + carry;

		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry++;
		}

		sumList.add_node(sum);

		num1 = num1->next;
		num2 = num2->next;
	}

	while (num1 != NULL) {
		sum = num1->data + carry;

		carry = 0;

		if (sum >= 10) {
			sum -= 10;
			carry++;
		}

		sumList.add_node(sum);

		num1 = num1->next;
	}

	while (num2 != NULL) {
		sum = num2->data + carry;

		carry = 0;

		if (sum >= 10) {
			sum -= 10;
			carry++;
		}

		sumList.add_node(sum);

		num2 = num2->next;
	}

	if (carry != 0) sumList.add_node(carry);

	return sumList;
}

int main() {
	linked_list list1;
	list1.add_node(3);
	list1.add_node(2);
	list1.add_node(1);
	list1.add_node(5);
	list1.add_node(4);
	list1.add_node(4);
	list1.add_node(1);
	list1.add_node(5);
	list1.add_node(6);
	list1.add_node(8);
	list1.add_node(1);
	list1.add_node(2);
	list1.add_node(9);

	list1.printLinkedList();

	linked_list list2;
	list2.add_node(3);
	list2.add_node(2);
	list2.add_node(1);
	list2.add_node(5);
	list2.add_node(4);
	list2.add_node(4);
	list2.add_node(1);
	list2.add_node(5);
	list2.add_node(6);
	list2.add_node(8);
	list2.add_node(1);
	list2.add_node(9);

	list2.printLinkedList();

	SumTwoList(list1, list2).printLinkedList();
}

리스트의 각 노드를 더해 올림수가 있을 경우 다음 노드를 계산할때 더해준다.

두 리스트를 모두 탐색한 상태에서 올림수가 남아있으면 마지막에 값이 1인 노드를 추가해준다.

---

노드의 NULL 체크를 while문 안에서 할 경우 while문을 1개로 줄일 수 있다.