[LeetCode] 2. Add Two Numbers (Python)
문제
두 개의 비어있지 않은 링크드 리스트가 주어진다.
각 노드는 0 또는 자연수로 채워져있다. 숫자는 역순으로 저장돼있고, 두 노드의 각 숫자의 합을 연결 리스트로 반환한다.
l1 = [2, 4, 3], l2 = [5, 6, 4]라면 결과는 [7, 0, 8]이 나와야 한다.
말 그대로 두 링크드 리스트에서 각 노드의 숫자를 합해서 하나의 노드로 만든다는 말이다.
2 + 5 = 7
4 + 5 = 10 이지만 제한 사항에 다음과 같은 내용이 있다. (0 <= Node.val <= 9)
10은 9보다 크기 때문에 1을 다음 두 노드 간의 합에 반영한다.
이렇게 342 + 464 = 807이라고 돼있는 설명이 더 헷갈리게 한다🤪
노드의 값이 0과 9사이 값이라는 걸 제한사항이 아닌 문제 위쪽에 적어주는 것이 덜 헷갈릴 것 같다.
풀이 과정
풀이 시간: 35분
알고리즘: 링크드 리스트
1. answer를 Dummy Node로 만들어 놓고, 현재 노드(cur) 역시 answer에서 시작한다.
2. l1과 l2에 val가 있다면 각 노드의 숫자를 꺼내와 합을 구한다.
3. 그 합을 노드로 만든 후 cur.next가 해당 노드를 가리키게 한다.
4. 현재 노드(cur)은 방금 만든 합 노드로 갱신한다.
시간 복잡도: O(max(n, m))
각 연결 리스트 순회: l1의 길이를 n, l2의 길이를 m이라고 한다면, 각 연결 리스트의 모든 노드를 순회하면서 링크드 리스트를 만들어야 하기 때문에 O(max(n, m))이 된다.
코드
from typing import Optional
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]:
"""
:param l1: first linked list
:param l2: second linked list
:return: sum of both linked lists
"""
flag = 0 # 자릿수 올림을 저장할 변수
answer = ListNode() # 더미 헤드 노드
current = answer
while l1 or l2 or flag:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# 현재 자리의 합 계산
total = val1 + val2 + flag
flag = 1 if total > 9 else 0
current.next = ListNode(total % 10)
# 다음 노드로 이동
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return answer.next재귀로도 풀이할 수 있는데 그냥 단순하게 cur 을 사용해서 구현했다.
Linked List 이용한 문제를 오랜만에 푸는데 재밌었다.
LeetCode는 미리 정의된 클래스 ListNode 와 같은 것들을 활용해서 문제를 풀어야 하는 경우들이 있어서 독특한 것 같다.
안그랬음 그냥 eval 사용해서 합 구한 후 리스트로 반환했을텐데, next에 다음 노드의 주소를 저장함으로써 논리적 연속성을 유지하는 링크드 리스트의 특성을 활용해 풀어야해서 재밌었다.