두 개의 단일 연결 목록 L1과 L2가 있다고 가정하고 각각은 최하위 자릿수를 나타내는 숫자를 먼저 나타내므로 합산 연결 목록을 찾아야 합니다.
따라서 입력이 L1 =[5,6,4] L2 =[2,4,8]과 같으면 출력은 [7, 0, 3, 1, ]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
캐리 :=0
-
res :=값이 0인 새 노드
-
curr :=res
-
L1이 비어 있지 않거나 L2가 비어 있지 않거나 캐리가 0이 아닌 동안 do
-
l0_val :=L1이 비어 있지 않으면 L1의 값, 그렇지 않으면 0
-
l1_val :=L2가 비어 있지 않으면 L2의 값, 그렇지 않으면 0
-
합계_ :=l0_val + l1_val
-
carry :=(sum_ + carry)의 몫 / 10
-
add_val :=(sum_ + carry) / 10의 나머지
-
curr.next :=값이 add_val인 새 노드
-
curr :=curr의 다음
-
L1 :=L1이 비어 있지 않으면 L1의 다음, 그렇지 않으면 null
-
L2 :=L2가 비어 있지 않으면 L2의 다음, 그렇지 않으면 null
-
-
curr의 다음:=null
-
res의 다음 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
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 solve(self, L1, L2):
carry = 0
res = ListNode(0)
curr = res
while L1 or L2 or carry:
l0_val = L1.val if L1 else 0
l1_val = L2.val if L2 else 0
sum_ = l0_val + l1_val
carry, add_val = divmod(sum_ + carry, 10)
curr.next = ListNode(add_val)
curr = curr.next
L1 = L1.next if L1 else None
L2 = L2.next if L2 else None
curr.next = None
return res.next
ob = Solution()
L1 = make_list([5,6,4])
L2 = make_list([2,4,8])
print_list(ob.solve(L1, L2)) 입력
[5,6,4], [2,4,8]
출력
[7, 0, 3, 1, ]