左神算法学习笔记 - 011【入门】链表入门题目-两个链表相加

【算法讲解011【入门】链表入门题目-两个链表相加】 https://www.bilibili.com/video/BV1bh4y1r75d/?share_source=copy_web&vd_source=939a5033dc1ec4f712d59a4a4042e169

继续一道链表题目，练习链表的处理。

Leetcode 链接

这道题目的要求是把给定的两个链表所代表的数字相加，而这两个链表的数字是倒序给的：

• list1 是 2 -> 4 -> 3，代表 342

• list2 是 5 -> 6 -> 4，代表 465

• 结果是 807，所以返回的结果链表应该是 7 -> 0 -> 8

这道题没有什么弯弯绕，直接按照数学上的加法进位规则，在链表上模拟这个过程就可以了。初次见的难点是如何处理进位，如何用代码写出来，会了之后就不难了。

左神的代码：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ans = null, cur = null;

        for (
            int sum, val, carry = 0;
            l1 != null || l2 != null || carry != 0;
            l1 = (l1 == null) ? null : l1.next,
            l2 = (l2 == null) ? null : l2.next
        ) {
            sum = (l1 == null ? 0 : l1.val)
                + (l2 == null ? 0 : l2.val)
                + carry;

            val = sum % 10;
            carry = sum / 10;

            if (ans == null) {
                ans = new ListNode(val);
                cur = ans;
            } else {
                cur.next = new ListNode(val);
                cur = cur.next;
            }
        }

        return ans;
    }
}

• 这里面最精妙的就是 for 循环的写法，判断条件和步进规则都和日常见到的 for 循环不一样

当然，评论区也有同学给出了用虚拟头节点的写法：

class Solution {
    public ListNode addTwoNumbers(ListNode h1, ListNode h2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;

        while (h1 != null || h2 != null || carry != 0) {
            int sum = (h1 == null ? 0 : h1.val) + (h2 == null ? 0 : h2.val) + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (h1 != null) h1 = h1.next;
            if (h2 != null) h2 = h2.next;
        }

        return dummy.next;
    }
}

• 这里也把 for 循环改成了 while，那么步进的条件就在循环体里处理

• 不过关于头节点，左神还是在评论区建议不要使用，因为工程上追求在自身上调整结构。个人认为刷题可以用。˚