Leetcode简易链表问题：为什么我的解决方案是错误的？（21.合并2个排序列表）

Question

问题：合并两个排序链表，并将其作为一个新的排序列表返回。新列表应该通过将前两个列表的节点拼接在一起来制作。

示例：输入：1-

我的解决方案：

/**
 * 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-

Answer 1

您的答案仅返回1-

下面是应该为您提供所需结果的代码

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))

Answer 2

您可以使用Sentinel节点，以便更轻松：

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

    let head = sentinel
    while (l1 && 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
    }
}

Answer 3

您遇到的问题的主要原因是函数的第三个参数：这与挑战的描述不一致。没有第三个参数。您需要创建不带此值的返回列表。

我知道您试图将部分结果作为第三个参数传递，并希望在每次递归调用中扩展该部分结果，但随后出现了问题：

首先，在前两个if块中，假设l3不是null，但您不能确定这一点。如果输入由空列表组成，代码将生成异常。

其次，如果l3表示包含多个元素的列表，则此代码将覆盖l3和l3之间的现有链接。接下来是原始的l3。接下来（以及随后的所有节点）将丢失。

尽管您可以通过首先在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));