문제 링크 : https://leetcode.com/problems/add-two-numbers/

1. Problem

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.

두 정수로 이루어진 LinkedList를 입력받아 각각의 정수를 합한 값을 다시 LinkedList로 반환

이 때 각 리스트는 정수의 역순을 뜻한다.

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]

Constraints:

* The number of nodes in each linked list is in the range [1, 100].
* 0 <= Node.val <= 9
* It is guaranteed that the list represents a number that does not have leading zeros.

2. Solution

2-1. 내 풀이 with 참고

# Definition for singly-linked list.
#class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
 #        self.next = next
class Solution:
    def addTwoNumbers(self, l1, l2):
        result = ListNode() # 빈 ListNode 생성
        pointer = result # ListNode를 가리키는 포인터, 처음은 비어있는 상태로 시작
        carry = 0 #올림수 초기화
        
        # l1 or l2의 자릿수가 남아있는 동안, 처리해야할 올림 수가 있는 동안
        while l1 or l2 or carry:  
            total = 0 # 각 자릿수의 합
            
            # ex) l1 = [2,4,3] 342
            if l1:
                total += l1.val # 2를 더하고
                l1 = l1.next # l1의 다음 자릿수인 4로 위치 이동
            # ex) l2 = [5,6,4]
            if l2:
                total += l2.val # 5를 더하고
                l2 = l2.next # l2의 다음 자릿수인 6으로 이동
            total += carry # 올림수가 있다면 더해준다. 1자리 수라 없음.
            carry = total // 10 # 각 자릿수의 합 + 올림수가 두자리라면 10으로 나눈 몫을 carry에 할당.
            
            total = total % 10 # total을 10으로 나눈 나머지 = carry로 넘어간 10을 뺀 해당 자리의 수
            pointer.next = ListNode(total) # 현재 가리키는 노드에 새로운 노드를 연결
            
            pointer = pointer.next # 현재 값의 다음으로 이동
            
        return result.next # 빈 노드 이후의 노드부터 리턴해준다

결과:

Time Complexity

Time Complexity = O(max(m,n))
length of l1 = m , length of l2 = n
l1, l2 둘 중 어느 노드가 더 많은지에 따라 최대 m * n번을 돌게 된다.

시뮬레이션 돌려보기
ex) l1 = [2,4,3] l2 = [5,6,4]
1회차 : carry = 0, l1.val = 2 l2.val = 5
total = 7
carry = 7 // 10 = 0
total = 7 % 10 = 7
pointer.next = ListNode(7) Node()(현재 pointer위치) - Node(7)
pointer = pointer.next => Node() - Node(7)(현재 포인터 위치)
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
2회차: carry = 0, l1.val = 4 l2.val = 6
total = 10
carry = 10 // 10 = 1
total = 10 % 10 = 0
pointer.next = ListNode(0) Node() - Node(7)(현재 포인터 위치) - Node(0)
pointer = pointer.next => Node() - Node(7) - Node(0)(현재 포인터 위치)
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
3회차: carry = 1, l1.val = 3 l2.val = 4
total = 7 + carry(1) = 8
carry = 8 // 10 = 0
total = 8 % 10 = 8
pointer.next = ListNode(8) Node() - Node(7) - Node(0)(현재 포인터 위치) - Node(8)
pointer = pointer.next => Node() - Node(7) - Node(0) - Node(8)(현재 포인터 위치)
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡwhile 종료ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
result = ListNode()
result.next = ListNode() | 여기서부터 - 7 - 0 - 8 리턴

LinkedList 개념은 아는데 구현하기가 생각보다 쉽지 않았다..
역시 머리로 아는거랑 직접해보는거랑 다른... 아이디어는 있는데 이걸 코드로 못 적으니까 답답.
개념을 좀 더 다지고 이걸 잘 구현해보는 것을 목표로...