Leetcode: добавление двух чисел, представленных в обратном связанном списке, не работает - PullRequest
Новая
       59

Leetcode: добавление двух чисел, представленных в обратном связанном списке, не работает

0 голосов
/ 15 мая 2018

Следующий код не работает для ввода ниже: [2,4,3] [5,6,4] Выход: [7,8] Ожидаемое: [7,0,8]

Почему я не получаю 0? Может кто-нибудь, пожалуйста, помогите мне. 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        return AddTwoNumbersHelper(l1, l2, 0);            
    }


private ListNode AddTwoNumbersHelper(ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null)
        return null;

    int temp = 0;
    if (l1 != null)
        temp += l1.val;

    if (l2 != null)
        temp += l2.val;

    ListNode result = new ListNode(temp % 10);
    carry = temp / 10;

    l1 = l1.next;
    l2 = l2.next;
    int sum = 0;
    while(l1 != null || l2 != null) {
        sum = carry;

        if (l1 != null)
            sum += l1.val;

        if (l2 != null)
            sum += l2.val;

        carry = sum == 0 ? 0 : sum / 10;
        sum = sum % 10;

        result.next = new ListNode(sum);
        if(l1 != null)
            l1 = l1.next;
        if(l2 != null)
            l2 = l2.next;
    }

    if (carry > 0)
        result.next = new ListNode(carry);

    return result;
}

}

1 Ответ

0 голосов
/ 25 февраля 2019

Некоторые недостатки с кодом:

  1. Вам не нужен параметр переноса в вашем методе, если вы не повторяете то, что вы не делаете.
  2. Список шагов продвижения (l = l.next) можно комбинировать с шагом, на котором вы добавляете значение узла в переменную temp (sum).
  3. Вам не нужно писать дополнительный код для обработки висящего переносадля этого вам достаточно цикла, просто включите условие в цикл.
  4. Ошибка в том, что вы постоянно обновляете следующий указатель головы, а не строите (добавляете один узел) к связанномусписок в каждой итерации.Вам нужен дополнительный указатель / переменная, чтобы сделать это.
  5. 'sum' - это лучшее имя переменной, чем 'temp'.

Вот несколько измененное решение, которое устраняет вышеуказанные проблемы: 

private ListNode AddTwoNumbersHelper(ListNode l1, ListNode l2) {

    ListNode result = null;
    ListNode tail = null;
    int carry = 0;
    while ((l1 != null) || (l2 != null) || (carry != 0)) {

        int sum = carry;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        carry = sum/10;
        sum %= 10;
        if (result == null) { // first time
            result = new ListNode(sum);
            tail = result;
        } else {
            tail.next = new ListNode(sum);
            tail = tail.next;
        }
    }
    return result;
}
...