LeetCode 2. Add Two Numbers

布满荆棘的人生 2022-05-27 07:30 120阅读 0赞

Description

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 contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
    Output: 7 -> 0 -> 8
    Explanation: 342 + 465 = 807.

--------------------

C/C++（C++写法和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) {
            struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
            //定义一个链表接收结果
            int tmp = 0;
            head->next = NULL;
            struct ListNode* t = head;
            while(l1||l2)
            {
                if(l1)
                {
                    tmp += l1->val;
                    l1 = l1->next;
                }
                if(l2)
                {
                    tmp += l2->val;
                    l2 = l2->next;
                }
                struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
                node->val = tmp%10;
                tmp/=10;
                node->next = t->next;
                t->next = node;
                t = t->next;
            }
            while(tmp)//当结果的长度超过最长的链时，向前进位
            {
                struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
                node->val = tmp%10;
                tmp/=10;
                node->next = t->next;
                t->next = node;
                t = t->next;
            }
            return head->next;
        }
    };

Java

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode ans = new ListNode(0);
            ListNode t = ans;
            int tmp = 0;
            while(l1!=null||l2!=null)
            {
                if(l1!=null)
                {
                    tmp += l1.val;
                    l1 = l1.next;
                }
                if(l2!=null)
                {
                    tmp += l2.val;
                    l2 = l2.next;
                }
                t.next = new ListNode(tmp%10);
                tmp/=10;
                t = t.next;
            }
            while(tmp!=0)
            {
                t.next = new ListNode(tmp%10);
                tmp/=10;
                t = t.next;
            }
            return ans.next;
        }

Python

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    
    class Solution:
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            ans = ListNode(0)
            t = ans
            tmp = 0
            while l1!=None or l2!=None:
                if l1!=None:
                    tmp += l1.val
                    l1 = l1.next
                if l2!=None:
                    tmp += l2.val
                    l2 = l2.next
                t.next = ListNode(tmp%10)
                tmp //= 10
                t = t.next
            while tmp!=0:
                t.next = ListNode(tmp%10)
                tmp //= 10
                t = t.next
            return ans.next