这是悦乐书的第340次更新,第364篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Medium级别的第1题(顺位题号是2)。给定两个非空链表,表示两个非负整数。 数字以相反的顺序存储,每个节点包含一个数字。将两个数字相加并将其作为链表返回。你可以假设这两个数字不包含任何前导零,除了数字0本身。例如:

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

输入:(2 -> 4 -> 3)+(5 -> 6 -> 4)
输出:7 -> 0 -> 8
说明:342 + 465 = 807。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

计算链表的节点值之和,包含以下两种情况:

  • 进位。两个节点值相加大于等于10后,会产生进位问题,需要将进位产生的数加到下一轮计算上去。如果是在最后一次计算产生进位,结果链表需要增加一个next节点。

  • 两链表的长度不相等时,可能会有一个链表先遍历完节点,而另外一个还剩下许多节点没遍历,因此在遍历的循环条件处,判空是或的关系,直到两个链表的节点都遍历完,才结束循环。

在此解法中,我们使用一个新的链表(头节点值为0)作为结果链表,使用一个boolean类型的变量flag来当做是否有进位的标志。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    ListNode tem = l1;
    ListNode tem2 = l2;
    ListNode current = result;
    boolean flag = false;
    while (tem != null || tem2 != null) {
        // 计算节点值之和,需要判空
        int sum = (tem != null ? tem.val : 0) + 
                (tem2 != null ? tem2.val : 0);
        // 有进位,节点值之和加1,flag变为false
        if (flag) {
            sum += 1;
            flag = false;
        }
        // 节点值之和大于等于10,只保留个位数,flag变为true
        if (sum >= 10) {
            sum -= 10;
            flag = true;
        }
        current.next = new ListNode(sum);
        current = current.next;
        if (tem != null) {
            tem = tem.next;
        }
        if (tem2 != null) {
            tem2 = tem2.next;
        }
    }
    // 尾节点可能因进位而产生
    if (flag) {
        current.next = new ListNode(1);
    }
    return result.next;
}


03 第二种解法

思路和上面一样,只是将计算进位换了一种方式来实现,采用了取余和整除的方式来实现。

public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    ListNode temp = result;
    int count = 0;
    while (l1 != null || l2 != null) {
        int sum = (l1 == null ? 0 : l1.val) +
                (l2 == null ? 0 : l2.val);
        sum += count;
        count = sum/10;
        temp.next = new ListNode(sum%10);
        temp = temp.next;
        if (l1 != null) {
            l1 = l1.next;
        }
        if (l2 != null) {
            l2 = l2.next;
        }
    }
    if (count > 0) {
        temp.next = new ListNode(count);
    }
    return result.next;
}


04 第三种解法

使用递归。

public ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    helper(result, l1, l2, 0);
    return result.next;
}

/**
 * 递归方法
 * @param result 结果链表
 * @param l1
 * @param l2
 * @param carry 进位产生的数
 */
public void helper(ListNode result, ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null) {
        return ;
    }
    int sum = (l1 == null ? 0 : l1.val) +
            (l2 == null ? 0 : l2.val);
    sum += carry;
    carry = sum/10;
    result.next = new ListNode(sum%10);
    result = result.next;
    if (l1 != null) {
        l1 = l1.next;
    }
    if (l2 != null) {
        l2 = l2.next;
    }
    if (l1 == null && l2 == null && carry > 0) {
        result.next = new ListNode(carry);
    }
    helper(result, l1, l2, carry);
}


05 第四种解法

对上面的递归方法,我们还可以再简化下,不借助额外的递归方法,以此方法本身做递归。

public ListNode addTwoNumbers4(ListNode l1, ListNode l2) {
    if (l1 == null && l2 == null) {
        return null;
    }
    int val = (l1 == null ? 0 : l1.val) +
            (l2 == null ? 0 : l2.val);
    ListNode result = new ListNode(val%10);
    result.next = addTwoNumbers4(l1 == null ? null : l1.next, 
            l2 == null ? null : l2.next);
    if (val >= 10) {
        result.next = addTwoNumbers4(result.next, new ListNode(1));
    }
    return result;
}


06 小结

算法专题目前已连续日更超过六个月,算法题文章209+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄