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

Пример: (2-›3-›4) + (2-›1-›3) [т. е. 432 + 312]

Ожидаемое решение: (4-›4-›7) [т. е. 432 + 312 = 744]

Первоначальные мысли:

  1. Должны ли мы сначала построить числа, вычислить сумму и преобразовать сумму в связанный список, который будет возвращен в качестве решения? Ну, это определенно не эффективное решение.
  2. Итак, учитывая эффективность, вероятно, хорошим подходом будет работа с одним циклом для одновременного обхода обоих связанных списков.

Подход 1:

Это задача с уровнем сложности средний. Поэтому имеет смысл строить решение поэтапно и импровизировать по ходу дела. К этому моменту мы установили, что будем использовать оператор цикла для обхода списков (оба списка одновременно). Этот цикл, вероятно, будет работать до тех пор, пока не будут исчерпаны узлы в самом длинном списке. Подождите минутку — если есть перенос, нам нужно запустить дополнительную итерацию, чтобы учесть и это.

Примечание. Результат также попадает в LinkedList с цифрами конечной суммы, хранящимися в обратном порядке. Это означает, что нам нужен один LinkedList, который будет возвращен как результат, указывающий на цифру в позиции единиц. И еще одна копия, которая будет использоваться для обхода и хранения суммы текущей позиции узла. Этот последний список будет использоваться для фактических вычислений.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int digitFromFirst;
        int digitFromSecond;
        int carryOver = 0;
        ListNode output = null;
        ListNode previousNode = null;
        while(l1!=null || l2!=null || carryOver!=0){
            digitFromFirst = digitFromSecond = 0;
            if(l1!=null){
                digitFromFirst = l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                digitFromSecond = l2.val;
                l2 = l2.next;
            }
            int currentSum = carryOver + digitFromFirst + digitFromSecond;
            if(output == null){
                output = new ListNode(currentSum%10);
                previousNode = output;
            } else {
                ListNode currentNode = new ListNode(currentSum%10);
                previousNode.next = currentNode;
                previousNode = currentNode;
            }
            carryOver = currentSum/10;
        }
        return output;
    }

Больше постов ищите здесь.

Удачи и Чао!