[leetcode题解]445. Add Two Numbers II

leetcode 445题,题目如下:
You are given two linked lists representing two non-negative numbers. The most significant digit comes first 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.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

思路:题目比较简单两链表相加的问题(linked list),不需要思考太多,直接把两个链表逆置一下,从前往后加就行,结果采用头插的方法直接逆置,这样最后就无需把结果逆置了,最后不要忘记进位就可以了。

代码如下:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        l1 = reverse(l1);
        l2 = reverse(l2);
        
        ListNode *pre = new ListNode(-1);
        
        ListNode *p1 = l1, *p2 = l2;
        int a = 0, b = 0, c = 0;
        
        while(p1 != NULL || p2 != NULL)
        {
            a = 0;
            if (p1 != NULL)
            {
                a = p1->val;
                p1 = p1->next;
            }
            
            b = 0;
            if (p2 != NULL)
            {
                b = p2->val;
                p2 = p2->next;
            }
            
            a = a + b + c;
            c = a / 10;
            a = a % 10;
            ListNode *node = new ListNode(a);
            node->next = pre->next;
            pre->next = node;
        }
        
        if (c != 0)
        {
            ListNode *node = new ListNode(c);
            node->next = pre->next;
            pre->next = node;
        }
        return pre->next;
    }
    
    ListNode *reverse(ListNode *l)
    {
        ListNode *pre = new ListNode(-1);
        
        ListNode *t = NULL;
        while(l != NULL)
        {
            t = l->next;
            l->next = pre->next;
            pre->next = l;
            l = t;
        }
        return pre->next;
    }
};

python代码:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        res = ListNode(-1)
        l1 = self.reverse(l1)
        l2 = self.reverse(l2)
        
        a, b, c = 0, 0, 0
        while l1 != None or l2 != None:
            a = 0
            if l1 != None:
                a = l1.val
                l1 = l1.next
            
            b = 0
            if l2 != None:
                b = l2.val
                l2 = l2.next
            a = a + b + c
            c = a // 10
            a = a % 10
            node = ListNode(a)
            node.next = res.next
            res.next = node
        
        if c != 0:
            node = ListNode(c)
            node.next = res.next
            res.next = node
        return res.next
        
        
    def reverse(self, l):
        pre = ListNode(-1)
        while l != None:
            t = l.next
            l.next = pre.next
            pre.next = l
            l = t
        return pre.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]445. Add Two Numbers II

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/49.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注