2개의 비어 있지 않은 연결 목록이 있다고 가정합니다. 이 두 목록은 음이 아닌 정수 두 개를 나타냅니다. 숫자는 역순으로 저장됩니다. 각 노드에는 하나의 숫자만 포함됩니다. 두 숫자를 더하고 결과를 연결 목록으로 반환합니다. 우리는 두 숫자에 숫자 0 자체를 제외하고는 선행 0이 포함되어 있지 않다고 가정합니다. 따라서 숫자가 120 + 230이면 연결 목록은 [0 → 2 → 1] + [0 → 3 → 2] =[0 → 5 → 3] =350이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 2개의 목록 l1과 l2를 가져옵니다. 헤드 및 온도를 null로 초기화
- c :=0
- l1과 l2가 모두 비어 있지 않은 목록인 반면
- l1이 비어 있지 않으면 a :=0으로 설정하고, 그렇지 않으면 a :=l1.val로 설정
- l2가 비어 있지 않으면 b :=0으로 설정하고, 그렇지 않으면 b :=l2.val로 설정
- n :=a + b + c
- n> 9이면 c :=1, 그렇지 않으면 0
- node :=값이 n mod 10인 새 노드 생성
- 머리가 null인 경우
-
헤드 :=노드 및 임시 :=노드
-
- 그렇지 않으면
- head.next :=노드 및 헤드 :=노드
- l1 :=l1이 존재하는 경우 l1의 다음 노드
- l2 :=l2가 있는 경우 l2의 다음 노드
- c가 0이 아니면
- 노드:=값이 1인 새 노드, 헤드 다음:=노드
- 반환 온도
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
head = None
temp = None
c = 0
while l1 or l2:
if not l1:
a= 0
else:
a = l1.val
if not l2:
b=0
else:
b = l2.val
n = a +b + c
c = 1 if n>9 else 0
node = ListNode(n%10)
if not head:
head = node
temp = node
else:
head.next = node
head = node
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
if c:
node = ListNode(1)
head.next = node
return temp
ob1 = Solution()
l1 = make_list([0,2,1])
l2 = make_list([0,3,2])
print_list(ob1.addTwoNumbers(l1, l2)) 입력
[0,2,1] [0,3,2]
출력
[0,5,3]