하단 Title 클릭 시 해당 문제 페이지로 이동합니다.
- Add Two Numbers
- Acceptance: 37.8%
- Difficulty: Medium
문제 설명
Linked list 형태의 컨테이너가 두 개 주어지고, 각 node에는 value가 비어있지 않으며 양수가 주어진다. 또한, node에는 해당 숫자가 역순으로 한 자리씩 들어있다. ex) 243 = 2 -> 4 -> 3.
두 개의 Linked list의 값을 더한 후, 해당 값을 Linked list에 한 자리씩 역순으로 넣은 결과를 return.
예시
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.문제 풀이
리스트당 node의 범위가 1 ~ 100 이므로 int나 long 타입으로 파싱해서 문제를 해결할 경우 runtime에 에러가 난다.
문제를 해결하기 위해서는 두 개의 list에서 node값을 더하여 result node에 하나하나 처리하는 방식을 이용해야 한다.
문제를 풀기 위해서 Linked list의 개념을 이해하고 몇몇 조건을 고려하면 된다.
고려할 사항
- 리스트 l1과 l2중 next가 하나라도 존재하면 계속 진행
- l1과 l2의 next가 모두 null 이더라도 이전
l1.val과l2.val의 합이 10 이상이라면 다음 node를 만들어 추가해야한다. - Linked list의 head값을 사전에 저장하여 return할 수 있도록 해야한다.
코드
/**
* 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) {
int carry = 0, total; // l1.val과 l2.val의 합이 10 이상인 경우 next node.val에 값을 더해주어야 함
ListNode head = new ListNode(), cur = head; // return을 위해 head값을 지정
while (l1 != null || l2 != null || carry > 0) {
total = 0;
cur.next = new ListNode(); // next node 생성
cur = cur.next; // cur = next node
// l1
if (l1 != null) {
total += l1.val;
l1 = l1.next;
}
// l2
if (l2 != null) {
total += l2.val;
l2 = l2.next;
}
total += carry;
carry = total / 10;
cur.val = total % 10;
}
return head.next; // head (비어있음) -> next (실제 시작)
}
}