[LeetCode] 2. Add Two Numbers : LinkedList

문제

 

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.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

---

 

배운점

 

LinkedList 한번도 안써봤다.. 공부해야겠다.

 

1. while 문에서 or 조건을 생각하지 못했다. or 조건을 쓰면 둘 중 하나라도 next가 있는 경우를 산정할 수 있다.

2. null check을 반드시 해준다.

3. 나누기(/)와 나머지(%)를 잘 사용하면 10진수의 자릿수별로 나눠서 분석이 가능하다. 2진수도 나누는 수만 변경해주면 유용하게 쓸 수 있을 것 같다.

4. 여기서는 reverse order 이므로 나머지값을 dummy의 next값으로 지정해준다. 예를 들어 8 + 7인 경우 5를 next값으로 지정하여 reverse order를 만드는 방식이다.

5. curr, carry등의 변수명을 지을 수 있다.

6. 결과의 구조가 LinkedList라면, 또는 LinkedList를 활용해야하는 상황이 왔을 때는 항상 dummyList를 생각하자.

7. LinkedList 구조를 계속 만들어내기 위해서는 next node 값을 먼저 만들고 나서 current 값을 next node로 매칭해주어야 한다.

8. 만들어진 linkedList의 첫 노드 객체를 return 하면 된다. 그 객체가 next 값으로 모든 node들을 갖는 구조이기 때문이다.

 

 

 

---

풀이

 

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

 

---

 

참조

 

1. Leetcode

https://leetcode.com/problems

 

 

2. LinkedList

https://psychoria.tistory.com/767