LeetCode Top Interview 150) Add Two Numbers

Question

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.

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.

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#       self.val = val
#       self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

---

---

바로 이전과 비슷한 입력이 들어오는 문제입니다. l1,l2 둘 다 링크드리스트의 헤드 노드입니다.
조건에서 숫자가 역순으로 들어 있다고 알려주고 있습니다.
복잡하게 생각할 거 없이 링크드리스트의 값이 일의 자리, 십의 자리, 백의 자리 순으로 나타난다고 생각하면 될 것 같습니다.
길이가 맞지 않을 때는 짧은 쪽이 숫자가 작아서 일찍 끝난다고 생각하면 됩니다.
그리고 두 링크드리스트의 더한 값도 같은 규칙으로 새로운 링크드리스트로 만들어주고 헤드노드를 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        new_node = ListNode()
        node = new_node
        while l1 != None or l2 != None:
            node = node.next if node.next != None else node

            node.val += l1.val if l1 != None else 0
            node.val += l2.val if l2 != None else 0

            node.next = ListNode(val=node.val//10)
            node.val = node.val%10

            l1 = l1.next if l1 != None else None
            l2 = l2.next if l2 != None else None
        
        if node.next.val == 0:
            node.next = None

        return new_node

• new_node : 반환하게될 링크드리스트의 헤드 노드입니다.
• node : 헤드 노드인 new_node는 반환용으로 두고 첫번째 노드를 포함하여 특정 노드를 가리키는 변수입니다.
• l1, l2 두 링크드리스트가 모두 끝날때까지 while문으로 순차 탐색합니다.
  • 이번 차례에 탐색이 끝난 노드의 다음 노드를 node로 다시 저장합니다. 맨 처음에는 다음 노드가 없으므로 조건문을 통해 예외처리 합니다.
  • l1,l2 두 노드 값의 합을 node값으로 저장합니다.
  • 10이상의 경우를 생각하며 다음 노드에 올려줄 값과 현재 값의 일의 자리를 저장합니다.
  • l1, l2의 노드를 다음 노드로 이동시킵니다. 다음 노드가 없는 경우 조건문을 통해 None으로 둡니다.
• 반복문을 탈출했다면 다음 노드의 값이 0인 경우에도 포인터가 노드를 가리킵니다. 올림값이 있어 1인 경우가 아니라면 불필요하므로 다음 노드를 없앴니다.
• 새롭게 생성한 노드의 헤드 노드를 반환합니다.

---

문제를 해결하는데 고민하는 것 보다..
단방향 링크드리스트여서 마지막에 남는 불필요한 0값 노드를 어떻게 효율적으로 없앨지 더 고민했던것 같습니다.
(새로운 다음 노드를 미리 지정해두지 않으면 헤드 노드를 처음에 정의하지 않아야 하는데 그러면 반환할 때 헤드노드를 찾기 번거롭기 때문에..)
마지막에 생각해낸 방법은,

1. 반복문이 시작될 때 현재의 노드를 불러옵니다. 다음 노드가 없어서 반복문이 시작되지 않을 때 노드를 굳이 이동시키지 않는 방법을 생각했습니다.
2. 반복문이 끝나면 다음 값에 따라 다음 노드를 둘 지, 아니면 None으로 초기화를 할 지 둡니다.

이 방법 전에는 새로운 반복문이 시작하기 전에 미리 노드를 옮겨놨는데 이것도 나름 첫 선언의 방식을 유지하기 위해 생각한 방법이라 방향을 트는데 방해되었습니다.

그 외에는 리스트를 순차적으로 살펴보며 올림만 생각해면 됐기에 알고리즘이 복잡하진 않았습니다!