Вопрос. Вам даны два непустых связанных списка, представляющих два неотрицательных числа. Цифры хранятся в обратном порядке, каждый узел содержит только одну цифру. Задача сложить два числа и вернуть решение в виде связанного списка, опять же, цифры хранятся в обратном порядке. Можно предположить, что ведущих нулей нет.
Пример: (2-›3-›4) + (2-›1-›3) [т. е. 432 + 312]
Ожидаемое решение: (4-›4-›7) [т. е. 432 + 312 = 744]
Первоначальные мысли:
- Должны ли мы сначала построить числа, вычислить сумму и преобразовать сумму в связанный список, который будет возвращен в качестве решения? Ну, это определенно не эффективное решение.
- Итак, учитывая эффективность, вероятно, хорошим подходом будет работа с одним циклом для одновременного обхода обоих связанных списков.
Подход 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; }
Больше постов ищите здесь.
Удачи и Чао!