← Static tasks

445. Add Two Numbers II

leetcode medium

#backtracking#csharp#leetcode#linked-list#medium

Task

Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Самый значимый разряд стоит первым, и каждый из их узлов содержит одну цифру. Сложите два числа и верните сумму в виде связанного списка.

Вы можете предположить, что оба числа не содержат начальных нулей, за исключением самого числа 0.

Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]

Output: [7,8,0,7]

C# solution

matched/original
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
public class Solution {
    private ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = ReverseList(l1);
        ListNode r2 = ReverseList(l2);
        int carry = 0;
        ListNode ans = null;
        while (r1 != null || r2 != null || carry > 0) {
            if (r1 != null) {
                carry += r1.val;
                r1 = r1.next;
            }
            if (r2 != null) {
                carry += r2.val;
                r2 = r2.next;
            }
            ListNode newNode = new ListNode(carry % 10);
            newNode.next = ans;
            ans = newNode;
            carry /= 10;
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
public:
    private ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = ReverseList(l1);
        ListNode r2 = ReverseList(l2);
        int carry = 0;
        ListNode ans = null;
        while (r1 != null || r2 != null || carry > 0) {
            if (r1 != null) {
                carry += r1.val;
                r1 = r1.next;
            }
            if (r2 != null) {
                carry += r2.val;
                r2 = r2.next;
            }
            ListNode newNode = new ListNode(carry % 10);
            newNode.next = ans;
            ans = newNode;
            carry /= 10;
        }
        return ans;
    }
}

Java solution

matched/original
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode temp = null;
        while (head != null) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = reverseList(l1);
        ListNode r2 = reverseList(l2);

        int totalSum = 0;
        int carry = 0;
        ListNode ans = new ListNode();
        while (r1 != null || r2 != null) {
            if (r1 != null) {
                totalSum += r1.val;
                r1 = r1.next;
            }
            if (r2 != null) {
                totalSum += r2.val;
                r2 = r2.next;
            }

            ans.val = totalSum % 10;
            carry = totalSum / 10;
            ListNode head = new ListNode(carry);
            head.next = ans;
            ans = head;
            totalSum = carry;
        }

        return carry == 0 ? ans.next : ans;
    }
}

JavaScript solution

matched/original
function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
}

var reverseList = function(head) {
    let prev = null;
    let temp = null;
    while (head !== null) {
        temp = head.next;
        head.next = prev;
        prev = head;
        head = temp;
    }
    return prev;
};

var addTwoNumbers = function(l1, l2) {
    let r1 = reverseList(l1);
    let r2 = reverseList(l2);

    let totalSum = 0;
    let carry = 0;
    let ans = new ListNode(0);
    while (r1 !== null || r2 !== null) {
        if (r1 !== null) {
            totalSum += r1.val;
            r1 = r1.next;
        }
        if (r2 !== null) {
            totalSum += r2.val;
            r2 = r2.next;
        }

        ans.val = totalSum % 10;
        carry = Math.floor(totalSum / 10);
        let head = new ListNode(carry);
        head.next = ans;
        ans = head;
        totalSum = carry;
    }

    return carry === 0 ? ans.next : ans;
};

Python solution

matched/original
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        temp = None
        while head:
            temp = head.next
            head.next = prev
            prev = head
            head = temp
        return prev

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        r1 = self.reverseList(l1)
        r2 = self.reverseList(l2)

        total_sum = 0
        carry = 0
        ans = ListNode()
        while r1 or r2:
            if r1:
                total_sum += r1.val
                r1 = r1.next
            if r2:
                total_sum += r2.val
                r2 = r2.next

            ans.val = total_sum % 10
            carry = total_sum // 10
            head = ListNode(carry)
            head.next = ans
            ans = head
            total_sum = carry

        return ans.next if carry == 0 else ans

Go solution

matched/original
type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    var temp *ListNode
    for head != nil {
        temp = head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    r1 := reverseList(l1)
    r2 := reverseList(l2)

    totalSum := 0
    carry := 0
    ans := &ListNode{}
    for r1 != nil || r2 != nil {
        if r1 != nil {
            totalSum += r1.Val
            r1 = r1.Next
        }
        if r2 != nil {
            totalSum += r2.Val
            r2 = r2.Next
        }

        ans.Val = totalSum % 10
        carry = totalSum / 10
        head := &ListNode{Val: carry}
        head.Next = ans
        ans = head
        totalSum = carry
    }

    if carry == 0 {
        return ans.Next
    }
    return ans
}

Explanation

Algorithm

Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем

ans.next

. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎