leetcode 2.两数相加(链表)

阅读数: 次 2020-04-25

题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解法

1.我的解法(仅供参考)

时间复杂度O(max(m,n))

假设m和n分别为l1和l2的长度，最多重复max(m,n)次

空间复杂度O(max(m,n))

新列表的长度最多为max(m,n)+1

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    ListNode cur = result;
    while(l1!=null&&l2!=null) {
        cur.val += l1.val + l2.val;
        if(l1.next!=null||l2.next!=null){
            cur.next = new ListNode(0);
        }
        if(cur.val>=10) {
            cur.val -=10;
            cur.next = new ListNode(1);
        }
        l1 = l1.next;
        l2 = l2.next;
        cur = cur.next;
    }
    if(l1==null) {
        while(l2!=null) {
            cur.val = l2.val;
            if(l2.next!=null) {
                l2 = l2.next;
                cur.next = new ListNode(0);
                cur = cur.next;
            }
        }
    }
    if(l2==null) {
        while(l1!=null) {
            cur.val = l1.val;
            if(l1.next!=null) {
                l1 = l1.next;
                cur.next = new ListNode(0);
                cur = cur.next;
            }
        }
    }
    return result;
}

这个算法在我本机上测试能够成功测试提交的测试数据，但是在官网提交时会提示超出时间限制。

主要缺陷：

判断不太行，中间经常会因为

1 2	cur.next = new ListNode(0); cur = cur.next;

这段代码之前没有加上充分的判断导致结果最后莫名其妙多出一个0，必须经常调试然后加l1/l2.next的判断，导致最后越绕越晕。

所以我的代码仅供参考，更多的是想分享一下我踩的坑和我这个菜逼从一开始读题目都懵逼到可以繁琐的写出算法的思路。

我的测试数据

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
    @Override
    public String toString() {
        return "ListNode [val=" + val + ", next=" + next + "]";
    }

@Test 
public void test() {
    ListNode l1 = new ListNode(2);
    l1.next = new ListNode(4);
    l1.next.next = new ListNode(3);
    ListNode l2 = new ListNode(5);
    l2.next = new ListNode(6);
    l2.next.next = new ListNode(4);
    ListNode result = Solution1.addTwoNumbers(l1, l2);
    System.out.println(result);
}
@Test 
public void test2() {
    ListNode l1 = new ListNode(0);

    ListNode l2 = new ListNode(1);

    ListNode result = Solution1.addTwoNumbers(l1, l2);
    System.out.println(result);
}

2.官方解法

时间复杂度O(max(m,n))

假设m和n分别为l1和l2的长度，最多重复max(m,n)次

空间复杂度O(max(m,n))

新列表的长度最多为max(m,n)+1

这里直接引用leetcode官方讲解

leetcode2

作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode pre = new ListNode(0);
    ListNode cur = pre;
    int carry = 0;
    while(l1!=null||l2!=null) {
        int x = l1==null ? 0:l1.val;
        int y = l2==null ? 0:l2.val;
        int sum = x+y+carry;
        carry = sum/10;
        sum = sum%10;
        cur.next = new ListNode(sum);
        cur = cur.next;
        if(l1!=null) {
            l1 = l1.next;
        }
        if(l2!=null) {
            l2 = l2.next;
        }
    }
    //这里可能最后一位相加大于10，但是while循环只能把最后一位数显示出来，所以需要判断要不要最后加个0
    if(carry==1) {
        cur.next = new ListNode(carry);
    }
    return pre.next;
}

精辟之处：

对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。

活用(判断条件)?x1:x2 真的可以简化好多代码

3.天皇解法：

学自评论区的mata川这位用户，有实力就是可以装bei：

维护一个进位变量t，还有比👴更短的吗？？

开始你的简化秀

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1), pre = dummyHead;
        int t = 0;
        while (l1 != null || l2 != null || t != 0) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            pre.next = new ListNode(t % 10);
            pre = pre.next;
            t /= 10;
        }

        return dummyHead.next;
    }
}