链表中的两数相加

发表于 | 分类于 ， ， |

​ 链表中的两数相加问题

2.两数相加 I

2

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
/**
 * 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) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p=dummy;
        //进位值
        int carry=0; 
        while(l1 || l2){
            //短的那个链表后面用0代替其值
            int l1_val = l1 ? l1->val : 0; 
            int l2_val = l2 ? l2->val : 0;
            
            //相加
            int sum = l1_val + l2_val + carry; 
            //更新
            carry = sum/10; 
            sum = sum%10; 

            p->next = new ListNode(sum);
            p = p->next;
            
            if(l1!=nullptr) l1=l1->next;
            if(l2!=nullptr) l2=l2->next;
        }
        //两个链表全部遍历完毕，进位值不为0，在链表后面添加一个新结点
        if(carry>0){
            p->next = new ListNode(carry);
        }
        return dummy->next;
    }
};
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
43
44
45
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: -1}
    p := dummy
    //进位值
    carry := 0
    for l1 != nil || l2 != nil {
        //短的那个链表后面用0代替其值
        l1_val := 0
        if l1 != nil {
            l1_val = l1.Val
        }
        l2_val := 0
        if l2 != nil {
            l2_val = l2.Val
        }
        
        //相加
        sum := l1_val + l2_val + carry
        //更新
        carry = sum / 10
        sum = sum % 10
        
        p.Next = &ListNode{Val: sum}
        p = p.Next
        
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }
    //两个链表全部遍历完毕，进位值不为0，在链表后面添加一个新结点
    if carry > 0 {
        p.Next = &ListNode{Val: carry}
    }
    return dummy.Next
}

445.两数相加 II

445

第一种方法：借助栈

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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //借助栈，逆序处理所有数位
        stack<int> st1, st2;
        while(l1){
            st1.push(l1->val);
            l1=l1->next;
        }
        while(l2){
            st2.push(l2->val);
            l2=l2->next;
        }

        ListNode* p=nullptr;
        int carry=0; //进位值
        while(!st1.empty() || !st2.empty()){
            int l1_val = st1.empty() ? 0 : st1.top();
            int l2_val = st2.empty() ? 0 : st2.top();
            if(!st1.empty()) st1.pop();
            if(!st2.empty()) st2.pop();

            int sum=l1_val+l2_val+carry;

            carry = sum/10;
            sum = sum%10;

            //反向建立单链表
            ListNode* cur = new ListNode(sum);
            cur->next = p;
            p = cur;

        }
        //两个链表全部遍历完毕，进位值不为0，再添加一个新结点
        if(carry>0){
            ListNode* cur = new ListNode(carry);
            cur->next = p;
            p = cur;
        }
        return p;
    }
};
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
43
44
45
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    //借助栈，逆序处理所有数位
    st1 := []int{}
    st2 := []int{}
    for l1 != nil {
        st1 = append(st1, l1.Val)
        l1 = l1.Next
    }
    for l2 != nil {
        st2 = append(st2, l2.Val)
        l2 = l2.Next
    }
    
    var p *ListNode
    carry := 0 //进位值
    for len(st1) > 0 || len(st2) > 0 {
        l1_val := 0
        if len(st1) > 0 {
            l1_val = st1[len(st1)-1]
            st1 = st1[:len(st1)-1]
        }
        l2_val := 0
        if len(st2) > 0 {
            l2_val = st2[len(st2)-1]
            st2 = st2[:len(st2)-1]
        }
        
        sum := l1_val + l2_val + carry
        
        carry = sum / 10
        sum = sum % 10
        
        //反向建立单链表
        cur := &ListNode{Val: sum}
        cur.Next = p
        p = cur
    }
    //两个链表全部遍历完毕，进位值不为0，再添加一个新结点
    if carry > 0 {
        cur := &ListNode{Val: carry}
        cur.Next = p
        p = cur
    }
    return p
}

第二种方法：借助反转链表

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
43
44
45
46
47
48
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reve(l1);
        l2 = reve(l2);
        ListNode* dummy=new ListNode(-1);
        ListNode* p=dummy;
        int carry=0;
        while(l1 || l2){
            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;
            
            int sum = val1+val2+carry;
            carry = sum/10;
            sum = sum%10;
            
            p->next = new ListNode(sum);
            p=p->next;
            
            if(l1){
                l1=l1->next;
            }
            if(l2){
                l2=l2->next;
            }
        }
        if(carry>0){
            p->next = new ListNode(carry);
        }
        return reve(dummy->next);
    }
    
    //反转单链表
    ListNode* reve(ListNode* head){
        if(head==nullptr) return nullptr;
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* nxt = cur->next;
    
            cur->next = pre;
            pre = cur;
            cur = nxt;
            
        }
        return pre;
    }
};
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
43
44
45
46
47
48
49
50
51
52
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    l1 = reve(l1)
    l2 = reve(l2)
    dummy := &ListNode{Val: -1}
    p := dummy
    carry := 0
    for l1 != nil || l2 != nil {
        val1 := 0
        if l1 != nil {
            val1 = l1.Val
        }
        val2 := 0
        if l2 != nil {
            val2 = l2.Val
        }
        
        sum := val1 + val2 + carry
        carry = sum / 10
        sum = sum % 10
        
        p.Next = &ListNode{Val: sum}
        p = p.Next
        
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }
    if carry > 0 {
        p.Next = &ListNode{Val: carry}
    }
    return reve(dummy.Next)
}

//反转单链表
func reve(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var pre *ListNode
    cur := head
    for cur != nil {
        nxt := cur.Next
        
        cur.Next = pre
        pre = cur
        cur = nxt
    }
    return pre
}

415.字符串相加

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
class Solution {
public:
    string addStrings(string num1, string num2) {
        int i=num1.size()-1;
        int j=num2.size()-1;
        int carry=0;
        string res="";
        while(i>=0 || j>=0 || carry!=0){
            int val1= i>=0 ? num1[i]-'0' : 0;
            int val2= j>=0 ? num2[j]-'0' : 0;

            int sum = val1+val2+carry;

            carry = sum/10;
            sum = sum%10;

            res.push_back(sum + '0');
            
            i--;
            j--;
        }
        reverse(res.begin(), res.end());

        return res;
    }
};
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
func addStrings(num1 string, num2 string) string {
    i := len(num1) - 1
    j := len(num2) - 1
    carry := 0
    res := ""
    for i >= 0 || j >= 0 || carry != 0 {
        val1 := 0
        if i >= 0 {
            val1 = int(num1[i] - '0')
        }
        val2 := 0
        if j >= 0 {
            val2 = int(num2[j] - '0')
        }
        
        sum := val1 + val2 + carry
        
        carry = sum / 10
        sum = sum % 10
        
        res = string(rune(sum+'0')) + res
        
        i--
        j--
    }
    
    return res
}
-------------本文结束 感谢阅读-------------
0%