Блог

Вопрос: Объединить два отсортированных связанных списка и вернуть его в виде нового отсортированного списка. Новый список должен быть создан путем объединения узлов первых двух списков.

Пример: Ввод: 1->2->4, 1->3->4 Вывод: 1->1->2->3->4->4

Мое решение:

 /**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

var mergeTwoLists = function(l1, l2, l3) {
    if (l2 === null) {
        l3.next = l1;
        return l3;
    }
    if (l1 === null) {
        l3.next = l2;
        return l3;
    }
    if (l2.val < l1.val) {
        if (l3) {
            l3.next = new ListNode(l2.val) 
        }
        else {
            l3 = new ListNode(l2.val)
        }
        return mergeTwoLists(l1, l2.next, l3)
    } else {
        if (l3) {
            l3.next = new ListNode(l1.val);
        }
        else {
            l3 = new ListNode(l1.val);
        }
        return mergeTwoLists(l1.next, l2, l3)
    }
};
  

Мой вывод просто 1-> 4 вместо 1->1->2->3->4->4. Кто-нибудь, пожалуйста, может сказать мне, почему?

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

Я понимаю, что вы пытались передать частичный результат в качестве третьего аргумента и хотите расширить этот частичный результат при каждом рекурсивном вызове, но затем все идет не так:

Во-первых, в первых двух if блоках вы предполагаете, что l3 не равно null, но вы не можете быть уверены в этом. В случае, если входные данные состоят из пустого списка, ваш код создаст исключение.

Во-вторых, если l3 представляет список, содержащий более одного элемента, то этот код перезапишет существующую связь между l3 и l3.next , и поэтому оригинал l3.next (и все последующие узлы) будут потеряны.

Хотя вы можете решить эту проблему, сначала найдя конечный узел в l3 , есть лучший способ. И этот лучший способ на самом деле является основным принципом хорошо продуманной рекурсии:

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

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

var mergeTwoLists = function(l1, l2) { // Only 2 parameters
    if (l2 === null) return l1; // don't prepend anything
    if (l1 === null) return l2; // don't prepend anything
    let node;
    if (l2.val < l1.val) {
        node = new ListNode(l2.val);
        node.next = mergeTwoLists(l1, l2.next);
    } else {
        node = new ListNode(l1.val);
        node.next = mergeTwoLists(l1.next, l2);
    }
    return node;
};

// Helper function for demo
const listFromArray = a => a.length ? new ListNode(a[0], listFromArray(a.slice(1)))  
                                    : null;

let l1 = listFromArray([1, 2, 4]);
let l2 = listFromArray([1, 3, 4]);
console.log(mergeTwoLists(l1, l2));  

Вы можете использовать сторожевой узел, чтобы это было намного проще:

 const mergeTwoLists = function(l1, l2) {
    const sentinel = {
        val: -1,
        next: null
    }

    let head = sentinel
    while (l1 amp;amp; l2) {
        if (l1.val > l2.val) {
            head.next = l2
            l2 = l2.next
        } else {
            head.next = l1
            l1 = l1.next
        }
        
        head = head.next
    }

    head.next = l1 || l2

    return sentinel.next
}
  

Если вы хотите сделать рекурсивно, нам не понадобится l3 :

 const mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2
    }

    if (l2 === null) {
        return l1
    }

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1

    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
}
  

Ваш ответ возвращается только 1->4 потому, что вы не повторяете свой недавно созданный объединенный список, т. Е. l3 . Вы непосредственно делаете l3.next=somevalue . Поскольку l3 это список, сначала вам нужно выполнить итерацию по нему и добавить значение или список в его последний узел, где l3.next будет null .

Вот код, который должен дать вам желаемый результат

 function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}
var mergeTwoLists = function(l1, l2, l3) {
  let addToMergedList = (l3, val) => {
    let rootNode = l3
    while (l3.next !== null)
      l3 = l3.next;
    l3.next = new ListNode(val);
    return rootNode;
  }
  if (l2 === null) {
    let root = l3
    if(!root)
      return l1
    while (l3.next)
      l3 = l3.next;
    l3.next = l1;
    return root;
  }
  if (l1 === null) {
    let root = l3
    if(!root)
     return l2
    while (l3.next)
      l3 = l3.next;
    l3.next = l2;
    return root;
  }
  if (l2.val < l1.val) {
    if (l3) {
      l3 = addToMergedList(l3, l2.val)
    } else {
      l3 = new ListNode(l2.val)
    }
    return mergeTwoLists(l1, l2.next, l3)
  } else {
    if (l3) {
      l3 = addToMergedList(l3, l1.val)
    } else {
      l3 = new ListNode(l1.val);
    }
    return mergeTwoLists(l1.next, l2, l3)
  }
};

let l1={val:1,next:{val:2,next:{val:4,next:null}}}
let l2={val:1,next:{val:3,next:{val:4,next:null}}
console.log(mergeTwoLists(l1, l2))