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]

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.

자료구조 : LinkedNode 이용

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

알고리즘을 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 객체 생성 및 데이터 추가

ListNode dummyHead = new ListNode(0);