[Algorithm] Add Two Numbers

Question:

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]
Explanation: 342 + 465 = 807.

 

음수가 아닌 두개의 정수를 가지는 링크드 리스트가 있고 각 숫자는 역순으로 저장되며 각 노드는 한자릿수를 가지고 있습니다. 두 숫자를 더해서 그 합을 링크드 리스트로 다시 반환하는 문제입니다.

 

Solution:

링크드 리스트의 크기를 모르기 때문에 while문으로 반복처리를 진행합니다. 두 노드의 합을 구하고 혹시 두 노드의 합에 올림수가 있다면 carry 변수에 담고 다음 노드합에 합산시킵니다. 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode temp = null;

        int carry = 0;

	// 루프를 통해 두 노드가 null이 아닐때까지 반복
        while (l1 is not null || l2 is not null)
        {
            int sum = carry;

            if(l1 is not null)
            {
                Console.WriteLine(l1.val);
                sum += l1.val;
                l1 = l1.next;
                
            }
            if(l2 is not null)
            {
                Console.WriteLine(l2.val);
                sum += l2.val;
                l2 = l2.next;
            }

            Console.WriteLine("sum = " + sum);

    // 두합에 올림수가 있는지를 확인합니다.
            ListNode node = new ListNode(sum % 10);
            carry = sum / 10;

            Console.WriteLine("carry = " + carry);

            if(temp == null)
            {
                temp = head = node; // 첫번째 노드의 값
            }
            else
            {
                temp.next = node;
                temp = temp.next;
            }
        }
        
        if(carry >0) // 아직 올림수가 있다면 마지막 노드에 저장
        {
            temp.next = new ListNode(carry);
        }
        
        return head;
    }
}

While loop would be a good approach to go as we are unaware of size of both the linked list. Also we need to handle carry in last if there are any carry from last sum operation in loop.