[数据结构与算法]超过100%，每日一题之leetcode002

1 再接再厉-leetcode—002

好的开始是成功的一半，好的第二次开始那就是成功百分之75了。leetcode第二题考察的是基本的链表操作。题目描述如下：

1.1 题目描述

2.2 示例

2 解法

2.1 解法一

思路： 采用两个指针分别指向两个输入数组，并进行同步遍历，直至遍历结束。
步骤：

1. 初始化指针l1,l2指向数组链表头部。初始化head空链表，用于存放返回结果。
2. 初始化临时变量sum，初始值为0。
3. sum加上指针l1所指向元素，若指针指向元素为空，则sum不变；
4. sum加上指针l2所指向元素，若指针指向元素为空，则sum不变。
5. sum除以10的余数存入链表，sum等于sum/10(sum结果整数)。
6. l1和l2指针向后移动，若存在元素不为空，则循环2~6步骤，若均为空，则循环结束。

（今天下班比较晚就只写一个解法了）
这题直接采用指针的遍历两个链表的思路比较清晰，但是容易陷入的边界条件下的处理困境中，把问题越写越复杂。重点在于两个指针所指向元素的处理上，不是直接将其相加，而是引入了一个临时变量，依次相加，比较好的处理了进位的问题。

代码实现（Go语言版）

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{Val:0}
    cur,sum := head,0
    for (l1 != nil || l2 != nil || sum > 0) {
        cur.Next = &ListNode{Val:0}
        cur = cur.Next
        if l1 != nil {
            sum = sum + l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum = sum + l2.Val
            l2 = l2.Next
        }
        cur.Val = (sum) % 10
        sum = sum / 10
    }
    return head.Next
}

上面所实现的代码效果很不错，在Go语言里，时间复杂度超过了100%，空间复杂度也超过了92.3%。

动画图解

更多内容欢迎关注：