LeetCode——Problem2:Add Two Numbers

这又过了一周了，总感觉刷这个好花时间呀。每次都一两个小时。让我不好安排时间。应该是我太菜了。对，没错，就是这样

1、题目

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

2、Python解法

我想的是先把链表转化为数字相加，再把结果数字转化为链表

以下是我写的全部代码

 1 #!/usr/bin/python3
 2 # -*- coding: utf-8 -*-
 3 #@author: Albert
 4 #@Time: 2018/8/13
 5 
 6 
 7 class ListNode(object):
 8      def __init__(self, x):
 9          self.val = x
10          self.next = None
11 
12 class Solution(object):
13     def addTwoNumbers(self, l1, l2): #求解
14         """
15         :type l1: ListNode
16         :type l2: ListNode
17         :rtype: ListNode
18         """
19         number1=self.getNumber(l1)
20         number2=self.getNumber(l2)
21         number=number1+number2
22         l=self.num2LinkedLists(number)
23         return l
24 
25 
26     def getNumber(self,l):  #将链表转化为数字
27         number = 0
28         item = 1
29         while(item):
30             number = number+l.val*item
31             item=item*10
32             l=l.next
33             if l==None:
34                 item=0
35         return number
36     def num2LinkedLists(self,num):  #将数字转化为链表
37 
38         value=num%10
39         rest=int(num/10)
40         l=ListNode(value)
41         if rest!=0:
42             value = rest % 10
43             rest = int(rest / 10)
44             l.next=ListNode(value)
45             temp=l.next
46             while(rest!=0):
47                 value=rest%10
48                 rest=int(rest/10)
49                 temp.next=ListNode(value)
50                 temp=temp.next
51         return l
52 
53 def makeLinkedList(n):  #将一个列表数字转化为题目要求的链表，按照个位，十位，百位的顺序
54     l = ListNode(n[0])
55     l.next = ListNode(n[1])
56     temp = l.next
57     for i in n[2:]:
58         temp.next = ListNode(i)
59         temp = temp.next
60     return l
61 
62 l1=makeLinkedList([2,4,3])
63 l2=makeLinkedList([5,6,4])
64 
65 a=Solution()
66 l=a.addTwoNumbers(l1,l2)
67 number=a.getNumber(l)
68 print(number)

接下来看大神解法

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def addTwoNumbers(self, l1, l2):
 9         """
10         :type l1: ListNode
11         :type l2: ListNode
12         :rtype: ListNode
13         """
14         head = l1
15         carry = 0
16         while 1:
17             temp_sum = l1.val + l2.val + carry 
18             l1.val = temp_sum % 10
19             carry = temp_sum // 10
20             if not (l1.next and l2.next):
21                 break
22             l1 = l1.next
23             l2 = l2.next
24         if not (l1.next or l2.next):
25             if carry == 1:
26                 l1.next = ListNode(1)
27             return head
28         lr = l2 if l1.next == None else l1
29         l1.next = lr.next
30         while l1.next:
31             l1 = l1.next
32             temp_sum = l1.val + carry
33             l1.val = temp_sum % 10
34             carry = temp_sum // 10
35         if carry == 1:
36             l1.next = ListNode(1)
37         return head

我第二个想到的算法是这个，就是借用小学算加法的思路。设置一个进位。

3、C语言解法

我尝试了，但是结构体的基础有点差。没有运行成功。这就直接贴大神的解法了。运行时间20ms

#define MAKE_NODE (struct ListNode *)malloc(sizeof(struct ListNode))
struct ListNode *add_one(struct ListNode *);
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *p = l1, *q = l2, *r = NULL;
    int carry = 0;
    struct ListNode *nh = NULL;
    long sum = 0;
    while (p != NULL && q != NULL) {
        struct ListNode *new = (struct ListNode *) malloc(sizeof(struct ListNode));
        sum = p -> val + q -> val + carry;
        if (sum >= 10) {
            sum -= 10;
            carry = 1;
        }
        else carry = 0;
        new -> val = sum;
        new -> next = NULL;
        if (nh == NULL) {
            nh = new;
            r = nh;
        } else {
            r -> next = new;
            r = new;
        }
        p = p -> next;
        q = q -> next;
    }
    if (p != NULL && q == NULL) {
        if (!carry) {
         r -> next = p;
            return nh;
        }  //other we have a carry
        p = add_one(p);
        r -> next = p;
        return nh;
    }
    else if (p == NULL && q != NULL) {
        if (!carry) {
            r -> next = q;
            return nh;
        }
        q = add_one(q);
        r -> next = q;
        return nh;
    }
   
    if (carry > 0) {
        r -> next = MAKE_NODE;
        (r -> next) -> val = 1;
        (r -> next) -> next = NULL;
        return nh;
    }
    return nh;    
}
struct ListNode *add_one(struct ListNode *h) {
    struct ListNode *p = h, *prev = NULL;

    int carry = 1;
    while (h != NULL) {

        h -> val += carry;
        if (h -> val > 9) {
            carry = 1;
            h -> val -= 10;
        }
        else {
            carry = 0;
        }
        prev = h;
        h = h -> next; 
    }
    if (carry > 0) {
        struct ListNode *new = MAKE_NODE;
        new -> val = 1;
        new -> next = NULL;
        prev -> next = new;
    }
    return p;
}

其中的算法都是按照加法的进位

我还是C语言基础都忘的差不多了，没有写对。

主要是这个申请内存。(struct ListNode *)malloc(sizeof(struct ListNode))

其实他这个算法稍微麻烦了点。又用了一个新的add_one函数。如果l1，l2数目不一样。直接在后面的时候还直接进位，假设另一个为0就好啦。

最近事贼多。唉~愁人。想上研的时候跨专业，需要补习的东西还有很多呀~