Add Two Numbers

LeetCode 2. Add Two Numbers

원문

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.

풀이

두 연결 리스트의 값을 앞부터 더한다.
이때 노드의 값은 한 자리 숫자여야 하므로 변수 carry를 두어 그 노드에서 받아 올림으로 더해야 하는 수를 저장한다.
둘 중 하나가 더 짧다면 짧은 쪽 순회가 다 끝나고 긴 쪽을 마저 순회한다.
순회가 완전히 끝났을 때 carry의 값이 양수라면 그 carry 값을 새로운 노드에 추가해 tail로 만들어준다.

코드

Python

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        linked = ListNode()
        head = linked
        linked.val = (l1.val + l2.val) % 10
        carry = (l1.val + l2.val) // 10
        l1 = l1.next
        l2 = l2.next

        while l1 or l2:
            if l1 and l2:
                value = (l1.val + l2.val + carry) % 10
                carry = (l1.val + l2.val + carry) // 10
                new = ListNode(val=value)
                linked.next = new
                linked = linked.next
                l1 = l1.next
                l2 = l2.next
            elif l1:
                value = (l1.val + carry) % 10
                carry = (l1.val + carry) // 10
                new = ListNode(val=value)
                linked.next = new
                linked = linked.next
                l1 = l1.next
            else:
                value = (l2.val + carry) % 10
                carry = (l2.val + carry) // 10
                new = ListNode(val=value)
                linked.next = new
                linked = linked.next
                l2 = l2.next

        if carry:
            new = ListNode(val=carry)
            linked.next = new
            linked = linked.next

        return head

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum = (l1.val + l2.val) % 10;
        int carry = (l1.val + l2.val) / 10;
        ListNode result = new ListNode(sum);
        ListNode answer = result;

        l1 = l1.next;
        l2 = l2.next;

        while (l1 != null && l2 != null) {
            sum = (l1.val + l2.val + carry) % 10;
            carry = (l1.val + l2.val + carry) / 10;
            ListNode node = new ListNode(sum);
            result.next = node;
            result = result.next;
            l1 = l1.next;
            l2 = l2.next;
        }

        while (l1 != null) {
            sum = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;
            l1.val = sum;
            result.next = l1;
            result = result.next;
            l1 = l1.next;
        }

        while (l2 != null) {
            sum = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;
            l2.val = sum;
            result.next = l2;
            result = result.next;
            l2 = l2.next;
        }

        if (carry != 0) {
            ListNode node = new ListNode(carry);
            result.next = node;
        }

        return answer;
    }