9/3 每日一題(鏈結串列, 將兩個鏈結的節點相加 回傳新鏈結)

 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.

 

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]

# Definition for singly-linked list.

class ListNode:

    def __init__(self, val=0,next=None):

        self.val = val

        self.next = next

class LinkedList:

#     def __init__(self,head=None):

#         self.head=head

#     def append(self,value):

#         data=ListNode(value) #已經是節點了

#         p=self.head

#         if not p:

#             self.head=data

#             return

           

#         while p.next:

#             p=p.next

#         p.next = data #加入到鏈結尾巴

   

#     def creat_list(self):

#         '遍歷節點,並新增到list中'

#         p=self.head

#         res=[]

#         while p:

#             res.append(p.data)

#             p=p.next

#         return res

# 這部分沒用到 因為返回的資料型態 必須是 ListNode 所以這部分沒有使用到

   

   

class Solution:

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

        p1=l1 #設定標頭

        p2=l2 #設定標頭

        res1=[]

        res2=[]

        while p1:

            res1.append(str(p1.val))

            p1=p1.next

        while p2:

            res2.append(str(p2.val))

            p2=p2.next

        res1.reverse()

        res2.reverse()

        # print(res1)

        # print(res2)

        x=int(''.join(res1))

        y=int(''.join(res2))

        res= list(str(x+y))

        res.reverse()

       

        cur=ListNode() #建立標頭

        current = cur #紀錄標頭

        for i in res:

            current.next = ListNode(int(i)) #指向目標

            current = current.next

        return cur.next  #cur是None, cur.next才開始是res