leetcode刷題第二天<兩數相加>

題目描述

給出兩個 非空 的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照 逆序 的方式存儲的，並且它們的每個節點只能存儲 一位 數字。

如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。

您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

首先是c++

最開始採用官方題解java該c++版本的，代碼如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* p = l1;
        ListNode* q = l2;
        ListNode* curr = dummyHead;
        int carry = 0;
        while (p != 0 || q != 0) {
            int x = (p != 0) ? p->val : 0;
            int y = (q != 0) ? q->val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            if (p != 0) p = p->next;
            if (q != 0) q = q->next;
        }
        if (carry > 0) {
            curr->next = new ListNode(carry);
        }
        return dummyHead->next;
    }
};

思路為申請一個新的鏈表空間進行存儲，然後分別進行鏈表的傳遞，接著判斷鏈表的值與0的關係返回，最後求和，然後%10取餘數，最後判斷餘數和和0的關係，然後返回即可

另外一種大佬解法

是申請兩個鏈表的空間，然後如果鏈表不為空進行遍歷相加，最後在判斷鏈表和餘數與9的關係，最後返回第二個鏈表空間。

代碼如下

class Solution 
{
public:
   
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
{
        ListNode* list_head= new ListNode(0);
       
 ListNode* list_node=list_head;
        
while(1)
        
{
            int sum=list_node->val;
       
 if(l1)
       
 {
            sum+=l1->val;
            l1=l1->next;
        }
        
if(l2)
       
 {
            sum+=l2->val;
            l2=l2->next;
        }
     
   list_node->val=sum%10;
        if(l1||l2||sum>9)
        
{
            list_node->next=new ListNode(sum/10);
            
list_node=list_node->next;
        }
       
 else{
            break;
        }
    }
   
   return list_head;
    }
};

最後再用python走下

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        add_num = 0
        new_list = ListNode(0)
        cur = new_list
        cur1 = l1
        cur2 = l2
        while cur1 or cur2:
            if cur1 and cur2:
                value = cur1.val + cur2.val + add_num
            elif cur1:
                value = cur1.val + add_num
            elif cur2:
                value = cur2.val + add_num
                
            cur.next = ListNode(value % 10)
            add_num = 0
            if value > 9:
                add_num = 1
            cur = cur.next
            if cur1:
                cur1 = cur1.next
            if cur2:
                cur2 = cur2.next
        if add_num:
            cur.next = ListNode(add_num)
            cur = cur.next
        return new_list.next