runtime 20 ms, beats 99.62% of cpp submissions
O(n) solution with explanation

tags: linked list

add two numbers

๐Ÿ“– description

็ตฆๅฎšๅ…ฉๅ€‹็ฏ€้ปž็‚บๆ•ธๅญ—็š„ linked list ๏ผŒๅฐ‡ๆฏๅ€‹็ฏ€้ปžไธ€ๅฐไธ€็›ธๅŠ ใ€‚

๐Ÿง  solution

็ฐกๅ–ฎ็š„้ปžๅฐ้ปžๅŠ ๆณ•๏ผŒไฝ†่ฆๆณจๆ„ๅˆฐๅนพๅ€‹ไธๅŒ็š„ case

  • list ็š„้•ทๅบฆไธ็›ธๅŒ
  • ้€ฒไฝๅ•้กŒ
  • ๆœ€้ซ˜ไฝ้€ฒไฝ้œ€่ฆๆ–ฐๅขž็ฏ€้ปž

โณ time complexity

้ๆญทๅ…ฉๆข list ไธฆ่จˆ็ฎ—ๅŠ ๆณ•
็ธฝๆ™‚้–“่ค‡้›œๅบฆ O(n)

๐Ÿ“ code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto head=new ListNode(0);
        auto head1=head;
        int carry=0;
        int sum;
        while(l1!=nullptr || l2!=nullptr || carry!=0){ 
            sum=0;
            if(l1!=nullptr){ // ็ขบไฟไธๆœƒ่ตฐ่ถ…้Ž
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=nullptr){
                sum+=l2->val;
                l2=l2->next;
            }
            sum+=carry;  // ๅŠ ไธŠไธŠไธ€ไฝ็š„้€ฒไฝ
            if(sum>=10){ // ็•ถ็™ผ็”Ÿ carry
                carry=1;
                sum-=10; // ็•ถๅ‰็ฏ€้ปž-10
            }
            else{
                carry=0; // ๆฒ’ๆœ‰็™ผ็”Ÿ carry
            }
            auto tmp=new ListNode(sum);
            head1->next=tmp;
            head1=head1->next;
        }
        return head->next;
    }
};