как добавить два списка или список ссылок в javascript - PullRequest
Новая
       59

как добавить два списка или список ссылок в javascript

0 голосов
/ 21 марта 2020

Я пытаюсь добавить два списка или linklist, используя javascript, вот ниже вопрос

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

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

    342 + 465 = 807
Make sure there are no trailing zeros in the output list
So, 7 -> 0 -> 8 -> 0 is not a valid response even though the value is still 807.

Я пробовал вот так 

function Node(data) {
    this.data = data
    this.next = null
}


let addTwoNumbers = function (A, B) {
    let currentA = A,
        currentB = B,
        carry = 0,
        root = null;

    function addElementInNewLinkList(val, carry) {
        if (root == null) {
            root = new Node(val)
        } else {
            let temp = root;
            while (temp.next !== null) {
                temp = temp.next;
            }
            temp.next = new Node(val)
        }
    }

    while (currentA != null || currentB != null) {
    let sum = currentA && currentB ? currentA.data + currentB.data + carry: currentB?currentB+carry:currentA?currentA+carry:0;

        if (sum > 10) {
            carry = sum % 10;
            sum = 0;
        } else {
            carry = 0
        }
        //create new linkList
        addElementInNewLinkList(sum, carry);
        if (currentA != null) currentA = currentA.next
        if (currentB != null) currentB = currentB.next

    }

    return root
}


console.log(addTwoNumbers({"data": 9, "next": {"data": 9, "next": {"data": 1, "next": null}}}, {"data": 1, "next": null}))

Я получаю этот вывод 

{"data":10,"next":{"data":"[object Object]0","next":{"data":"[object Object]0","next":null}}}

Я не знаю, где я делаю не так.

Мой подход Мой подход состоит из двух добавлений, если сумма больше 10, затем нести (используя остаток)

после рефакторинга .UPDATE 

function Node(data) {
    this.data = data
    this.next = null
}


let addTwoNumbers = function (A, B) {
    let currentA = A,
        currentB = B,
        carry = 0,
        root = null;

    function addElementInNewLinkList(val, carry) {
        if (root == null) {
            root = new Node(val)
        } else {
            let temp = root;
            while (temp.next !== null) {
                temp = temp.next;
            }
            temp = new Node(val)
        }
    }

    while (currentA != null || currentB != null) {
        let sum = currentA && currentB ? currentA.data + currentB.data + carry: currentB?currentB+carry:currentA?currentA+carry:0;
        if (sum >= 10) {
            carry = sum % 10;
            sum = 0;
        } else {
            carry = 0
        }
        //create new linkList
        addElementInNewLinkList(sum, carry);
        if (currentA != null) currentA = currentA.next
        if (currentB != null) currentB = currentB.next

    }


    console.log(JSON.stringify(root))
    return root
}

Теперь я получаю этот

Узел {data: 0, next: null}

1 Ответ

0 голосов
/ 21 марта 2020

После отладки я обнаружил несколько проблем. Через некоторое время я смог решить свою проблему 

let addTwoNumbers = function (A, B) {
    let currentA = A,
        currentB = B,
        carry = 0,
        root = null;

    function addElementInNewLinkList(val) {
        if (root == null) {
            root = new Node(val)
        } else {
            let temp = root;
            while (temp.next !== null) {
                temp = temp.next;
            }
            temp.next = new Node(val)
        }
    }

    while (currentA != null || currentB != null) {
        let sum = currentA && currentB ? currentA.data + currentB.data + carry: currentB?currentB.data+carry:currentA?currentA.data+carry:0;
        if(sum==10){
            carry =  1;
            sum = 0
        } else if (sum > 10) {
            carry = Math.floor(sum / 10);
            sum = sum % 10;
        } else {
            carry = 0
        }
        //create new linkList
        addElementInNewLinkList(sum);
        if (currentA != null) currentA = currentA.next
        if (currentB != null) currentB = currentB.next

    }

 if(carry !==0)addElementInNewLinkList(carry);
    return root
}

Но я получаю предупреждение

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

...