[LeetCode/C#] Add Two Numbers

문제 출처 : https://leetcode.com/problems/add-two-numbers/description/

 

 

[문제]

두 개의 비어있지 않은 연결 리스트가 주어지며, 각각 두 개의 비음수 정수를 나타냅니다.

 

(1) 각 노드에는 한 자리 숫자가 포함되어 있습니다.

(2) 숫자는 역순으로 저장되어 있으므로, 연결 리스트의 첫 번째 노드는 숫자의 1의 자리를 나타냅니다.

 

이 두 숫자를 더한 결과를 새로운 연결 리스트로 반환하세요.

 

[조건]

입력되는 숫자는 0 이외에는 앞에 불필요한 0이 없습니다.

(예: 0012와 같은 숫자는 없으며, 유효한 숫자는 12, 0 등입니다.)

 

/**
 * 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 dummy = new ListNode(0);
        ListNode current = dummy; // 결과 리스트를 작성하는 현재 노드
        int carry = 0; // 자리올림(carry)을 저장하는 변수

        // 두 리스트(l1, l2)와 carry가 모두 0이 될 때까지 반복
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry; // 이전 자리에서의 carry 값을 현재 합계에 추가

            // l1 노드가 남아 있다면 현재 값(l1.val)을 합계에 추가하고 다음 노드로 이동
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            // l2 노드가 남아 있다면 현재 값(l2.val)을 합계에 추가하고 다음 노드로 이동
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            // 현재 자리의 합계를 10으로 나눈 몫은 carry로 저장 (다음 자리로 넘길 값)
            carry = sum / 10;

            // 현재 자리의 값은 10으로 나눈 나머지로 설정하여 새 노드로 추가
            current.next = new ListNode(sum % 10);

            // 결과 리스트의 다음 노드로 이동
            current = current.next;
        }

        // 더미 노드의 다음 노드가 결과 리스트의 시작점
        return dummy.next;
    }
}

 

 

[시간 복잡도]

O(max(n,m))

: n과 m은 각각 l1과 l2의 길이입니다.

 두 연결 리스트의 모든 노드를 한 번씩 순회하기 때문에, 더 긴 리스트의 길이에 비례합니다.