LeetCode攀登之旅(1)

公众号guangcity

发布于 2019-09-20 15:25:07

7340

发布于 2019-09-20 15:25:07

文章被收录于专栏：光城(guangcity)光城(guangcity)

LeetCode攀登之旅(1)

1.题目

2.解法

2.1 解法一

2.2 解法二

3.结果

4.作者的话

1.题目

Question:

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

Example:

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

2.解法

2.1 解法一

【Thinking:】

特殊情况:

两个链表开头均为0，直接返回其中一个链表即可；第一个链表开头为0，第二个链表开头不为0，返回第二个链表；第一个链表开头不为0，第二个链表开头为0，返回第一个链表。

其他情况如下：

如上例子所示得到807，然后逆向翻转即可得到7->0->8,那么怎么得到807呢，这个直接看上面Explanation：342+465，那么342与564又怎么得到呢？

很简单，分别对两个链表逆转组合的数即为这两个数，那么在链表操作，又如何得到这两个数？

以其中一个数字342为例子，他是由2*1+4*10+3*100得到的，那么只需要设置个参数t，首次赋值t=1,后面每次乘以10，作累加即可。另外一个数字同此方法，那么两数相加得到807，怎么展开成7、0、8，并分别赋给链表节点呢。

将807每次除以10，所得的余数刚好为7，继续以807/10的结果按照前面操作依次得到0、8；
在每次得到的数字7或者0、8的同时，可通过创建动态链表节点，并赋值即可。

到这里就有问题了，你怎么保证两数相加所得到的数不超过int范围。。。万一所给的链表很长，岂不是一下子就越界了。。那么以下代码运行就出现了这种问题。。所以不建议。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *s, *r=p;  //r 为表尾指针
    int t=1;
    int a=0,b=0,c;
    if(l1->val==0&&l2->val==0)
    {
        return l1;
    }
    else if(l1->val==0&&l2->val!=0)
    {
        return l2;
    }
    else if(l1->val!=0&&l2->val==0)
    {
        return l1;
    }
    else
    {
        while(l1)
        {
            a += t*(l1->val);
            l1 = l1->next;
            t *= 10;
        }
        t=1;
        while(l2)
        {

            b += t*(l2->val);
            l2 = l2->next;
            t *= 10;
        }
        c = a + b;
        while(c)
        {
            s=(struct ListNode *)malloc(sizeof(struct ListNode));
            s->val=c%10;
            r->next=s;
            r=s;  
            c=c/10; 
        }
        r->next = NULL;
        return p->next;

    }

}

2.2 解法二

【Thinking:】

特殊情况：链表一为空，返回链表二；链表二为空，返回链表一；

当链表一或者链表二一开始都不为空时，思考如下：

# 正方向直接算结果
(2 -> 4 -> 3)
(5 -> 6 -> 4)
(7 -> 0 -> 8)

那就是，当对应位置上的数相加超过10，就会使得下一位+1，有点类似于普通的两数相加，只不过反过来了。看出以上规律了？

那么我们这里很明确，因为当前位置上的数，最多两个9，和最大18，向后进位最多1，也就是当前位置上的两个数之和只要超过10，那么让他往后加上一个flag数即可，此处的flag为0或者1。

当前位置最终的数为两个链表对应位置数之和除以10的余数！

下一位是否进位通过前面一位对应两个链表相加，除以10的结果向前取整！

【c语言实现】

那么接下来，进入算法实现环节，首先来看c语言实现：

定义一个头结点head，并赋初值为0，可以不赋值；
定义动态节点s，此节点对应的值为每次两链表运算所得的数；
定义r节点，表示尾节点，采用尾插法，每次链向s；
特殊情况处理；
两链表循环内部操作；
利用尾节点直接指向头节点的下一个节点，并释放头结点，返回r所指的head的下一个节点，即为最终结果。

struct ListNode * addTwoNumbers( struct ListNode * l1, struct ListNode * l2 )
{
    struct ListNode * head, *r, *s;
    int tr;
    head = (struct ListNode *)malloc( sizeof(struct ListNode) );
    head->val = 0;
    r = head;
    if (l1 == NULL)
        return(l2);
    if (l2 == NULL)
        return(l1);
    int tsum;
    int flag = 0;
    while (l1||l2)
    {
        tsum = 0;
        if (l1)
        {
            tsum += l1->val;
            l1 = l1->next;
        }
        if (l2)
        {
            tsum += l2->val;
            l2 = l2->next;
        }
        tr = (tsum + flag) % 10;
        flag = (int) ( (tsum + flag) / 10);
        s = (struct ListNode * ) malloc( sizeof(struct ListNode) );
        s->val = tr;
        r->next = s;
        r = r->next;
    }
    if ( flag )
    {
        s = (struct ListNode *)malloc( sizeof(struct ListNode) );
        s->val = 1;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    r = head->next;
    free(head);
    return(r);
}

【python语言实现】

c与py链表操作不同

python链表操作与c语言链表操作不同，在python中直接使用ListNode(0)即可表示为当前节点赋值为0,并同时创建了当前节点。同理，c语言与python语言的next操作也不一样！

整除，c语言中使用int强制从float转换，而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
        """
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = ListNode(0)
        r = head
        flag=0
        while l1 or l2:
            tsum = 0
            if l1:
                tsum += l1.val
                l1=l1.next
            if l2:
                tsum += l2.val
                l2=l2.next
            tr = ((tsum + flag) % 10)
            flag = ((tsum + flag) // 10)
            r.next = ListNode(tr)
            r = r.next
        if flag:
            r.next = ListNode(1)
        r = head.next
        del head
        return r