前前后后做了不少项目,但是数据结构与算法这里还是有欠缺,最近也在边做边看,也简单记录一下题解吧~

题目如下:

两数相加

这个题目可以算是很常见的题了,在去年面阿里暑期实习的时候遇到过,这里重新做一下和大家分享吧。

首先是解读题目,需要注意一点很重要的地方:逆序,就是说两个链表的起始节点都代表个位,接下来的每一个节点都是对应的,这样的话就很好通过正常加法的形式来实现,只需要同步遍历两个链表即可,到10进1,如果两个链表不一样长的话只需要添加为0的节点继续计算即可。代码如下:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    let l1Cur = l1
    let l2Cur = l2
    let up = false
    let flag = false
    while ((l1Cur && !flag) || (l2Cur)) {
        l1Cur.val += (l2Cur ?.val || 0) + (up ? 1 : 0)
        up = false
        if (l1Cur.val > 9) {
            up = true
            l1Cur.val -= 10;
        }
        if ((!l1Cur.next) && (l2Cur?.next)) {
            flag = true
            l1Cur.next = new ListNode(0)
        }
        // 同步链表位置 同时定义退出时规则
        if (l1Cur) {
            if ((!l1Cur.next) && up) {
                // 这里新加一是为了了l1结束时添加上未进的位
                l1Cur.next = new ListNode(1)
                break
            }
            l1Cur = l1Cur.next
        }
        if (l2Cur) {
            l2Cur = l2Cur.next
        }
    }
    return l1
};
2人点赞