학습 목표
•
단일 연결 리스트(ListNode)의 기본 구조와 순회 방법을 이해한다.
•
자리수별 덧셈에서 발생하는 올림(carry) 개념을 이해하고 구현한다.
요구사항 분석
두 개의 역순 연결 리스트로 표현된 숫자를 더하는 문제
구분 | 내용 |
기능 요구사항 | - 두 개의 단일 연결 리스트(l1, l2)를 입력으로 받는다.
- 각 리스트는 숫자를 역순으로 저장한다.
- 두 리스트가 표현하는 숫자를 더한다.
- 합산 결과를 역순으로 저장한 새 연결 리스트를 반환한다. |
프로그래밍 요구사항 | - 입력과 출력은 ListNode 타입으로 처리한다.
- 마지막 carry가 남으면 새 노드를 생성한다. |
제약조건 | - 리스트 길이는 1~100이다.
- 각 노드: val (0~9), next (다음 노드 참조)
- 각 노드에는 0~9 범위의 정수가 저장된다.
- 선행 0이 없다(숫자 0 자체 제외). |
입출력 예시
•
일반적인 케이스
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Plain Text
복사
•
예외 케이스: 두 숫자 모두 0일 경우
Input: l1 = [0], l2 = [0]
Output: [0]
Plain Text
복사
•
예외 케이스: 마지막 덧셈에서 올림이 남은 경우
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Plain Text
복사
요구사항 설계
1.
Dummy Head 노드 생성
•
결과 리스트의 시작 부분 처리를 단순하게 하기 위해 dummy 노드를 하나 만든다.
2.
리스트 순회 -
•
두 입력 리스트를 동시에 탐색하면서 각 자리의 값을 더한다.
•
현재 자리의 합에 carry를 더해 새 노드를 생성한다.
•
자리수 합을 10으로 나눠 digit과 carry로 구분한다.
3.
마지막 Carry 처리
•
모든 노드를 처리한 뒤에도 carry가 남아 있으면, 이를 담은 노드를 하나 더 붙인다.
4.
리턴
•
dummy.next를 반환해 최종 결과 리스트의 시작점을 돌려준다.
요구사항 구현
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
const dummy = new ListNode();
let node = dummy;
let carry = 0;
while (l1 || l2 || carry) {
let sum = carry;
if (l1) {
sum += l1.val;
l1 = l1.next;
}
if (l2) {
sum += l2.val;
l2 = l2.next;
}
carry = Math.floor(sum / 10);
node.next = new ListNode(sum % 10);
node = node.next;
}
return dummy.next;
};
JavaScript
복사
