算法 LC 链表-两数相加

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头

示例1:
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

题解

思路1:模拟
由于链表都是逆序存储数字的位数的，因而链表的头部是低位数，尾部是高位数。因而可以直接将两个链表中同一位置的数字相加即可
又由于结果链表的每个节点都只能存储一位数字，因而我们考虑下进位值

// OC
+ (ListNode *)addTwoNumbers:(ListNode *)l1 l2:(ListNode *)l2 {
    // 哨兵节点
    ListNode *rootNode = [[ListNode alloc] initWithVal:-1 next:nil];
    // 进位数 0 1
    int flag = 0;
    
    // 遍历 临时节点
    ListNode *curNode = rootNode;
    ListNode *curl1 = l1;
    ListNode *curl2 = l2;
    
    // 如果curl1 curl2均为空，但存在进位数，需要再加个节点
    while (curl1 != nil || curl2 != nil || flag) {
        int a = (curl1 ? curl1.val : 0) + (curl2 ? curl2.val : 0) + flag;
        // 计算完成后 flag重置为0
        flag = 0;
        if (a > 9) {
            a = a - 10;
            flag = 1;
        }
        
        ListNode *tempNode = [[ListNode alloc] initWithVal:a next:nil];
        curNode.next = tempNode;
        curNode = curNode.next;
        
        curl1 = curl1.next;
        curl2 = curl2.next;
        
    }

    return rootNode.next;
}

// Swift
    static public func addTwoNumbers(_ l1:ListNode?, _ l2:ListNode?) -> ListNode? {
        // 哨兵节点
        let rootListNode = ListNode(-1)
        // 进位数0,1
        var flag = 0
        var curNode = rootListNode
        var curl1 = l1
        var curl2 = l2
        while curl1 != nil || curl2 != nil || flag == 1 {
            var a = (curl1?.val ?? 0) + (curl2?.val ?? 0) + flag
            flag = 0
            if a > 9 {
                a = a-10
                flag = 1
            }
            
            let nextNode = ListNode(a)
            curNode.next = nextNode
            curNode = nextNode
            
            curl1 = curl1?.next
            curl2 = curl2?.next
        }
        
        return rootListNode.next
    }

参考：https://leetcode-cn.com/problems/add-two-numbers