> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/linked-list/add-two-numbers.md).

# Add Two Numbers

2020.12.08 조흔나 링크드리스트 학습

You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order**, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

> Example 1:\
> Input : l1 = \[2,4,3], l2 = \[5,6,4]\
> Output : \[7,0,8]\
> 설명 : 342 + 465 = 807
>
> Example 2 :\
> Input : l1 = \[0], l2 = \[0]\
> Output : \[0]
>
> Example 3 :\
> Input : l1 = \[9,9,9,9,9,9,9], l2 = \[9,9,9,9]\
> Output : \[8,9,9,9,0,0,0,1]

{% hint style="info" %}
**Constraints** :

* The number of nodes in each linked list is in the range \[1,100].
* 0 <= Node.val <= 9
* It is guaranteed that the list represents a number that does not have leading zeros.
  {% endhint %}

자료구조 : LinkedNode 이용

알고리즘\
1\. Input ListNode를 가져와서 바로 사용 및 조작하지 않고, 복사한다.\
&#x20;  ListNode p = inputLN1 ,ListNode q = inputLN2;\
&#x20;  int x = p.val; int y = q.val;\
2\. 각 자리수의 합 sum = x + y + carry;\
&#x20;  carry = sum/10;\
&#x20;  **result.next = new ListNode(sum % 10);//새로운 노드를 생성하여 붙인다.**\
3\. 다음 노드로 이동 : p = p.next; q = q.next; result = result.next;

**알고리즘을 Java로 구현**\
**\* 더미노드를 사용하는 이유 : 더미노드를 사용하지 않아도 되지만, 헤드노드에 해당하는 노드를 삭제/추가/삽입할 때 포인터 처리를 일일히 다 해줘야한다. 하지만 더미노드를 사용하여 더미노드 뒤에 노드를 추가/삭제/수정하게 되면 코드를 일반화하여 일관성 있게 쓸 수 있기 때문에 더미노드를 사용한다.**

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //1.자료구조 생성
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;//정답이 되는 curr링크드리스트의 주소는 더미노드 주소로 고정!
        ListNode p = l1, q = l2;
        int carry = 0, sum = 0;
        
        //2.자릿수별로 더해서 sum을 저장한다!
        while(p != null || q != null) {//p가 null이 아니거나 q가 null이 아니라면(둘 중 하나라도 null이 아니면)
            int x = p != null ? p.val : 0;
            int y = q != null ? q.val : 0;
            sum = x+y+carry;
            carry = sum/10;
            curr.next = new ListNode(sum%10);
            curr = curr.next;
            if(p.next != null) p = p.next;
            if(q.next != null) q = q.next;   
        }
        if(carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}
```

**배운 내용 정리**\
Java에서 링크드리스트 사용하는 방법\
1\. LinkedNode 객체 생성 및 데이터 추가

```java
ListNode dummyHead = new ListNode(0);
```

<br>