Javascript常见算法（每日两个）

合并两个有序链表 

在JavaScript中，合并两个有序链表通常指的是将两个已经按照某种顺序（如升序或降序）排列的链表合并成一个新的有序链表。由于JavaScript本身不直接支持链表数据结构，我们通常会用对象或数组来模拟链表的行为。但为了更贴近链表的概念，我们可以使用对象来模拟链表节点，并通过指针（在JavaScript中通常是对象的引用）来连接这些节点。

链表节点的定义

首先，我们需要定义一个链表节点的结构。每个节点通常包含两部分：存储的数据（如数字、字符串等）和一个指向下一个节点的指针（在JavaScript中是一个对下一个节点对象的引用）。

链表节点的定义

首先，我们需要定义一个链表节点的结构。每个节点通常包含两部分：存储的数据（如数字、字符串等）和一个指向下一个节点的指针（在JavaScript中是一个对下一个节点对象的引用）。

function ListNode(val, next = null) {  this.val = val;  this.next = next;  
}

合并两个有序链表

合并两个有序链表的基本思路是使用两个指针分别遍历这两个链表，比较当前指针所指向的节点的值，将较小的节点添加到结果链表的末尾，并移动该指针到下一个节点。重复这个过程，直到两个链表都被遍历完。

function mergeTwoLists(l1, l2) {  // 创建一个哨兵节点，方便处理边界情况  let dummy = new ListNode(0);  let current = dummy;  // 当两个链表都不为空时，进行合并  while (l1 !== null && l2 !== null) {  if (l1.val < l2.val) {  current.next = l1;  l1 = l1.next;  } else {  current.next = l2;  l2 = l2.next;  }  current = current.next;  }  // 如果l1还有剩余节点，直接连接到结果链表的末尾  if (l1 !== null) {  current.next = l1;  }  // 如果l2还有剩余节点，直接连接到结果链表的末尾  if (l2 !== null) {  current.next = l2;  }  // 返回哨兵节点的下一个节点，即合并后的链表的头节点  return dummy.next;  
}

示例

假设我们有两个有序链表l1和l2，分别表示如下：

• l1: 1 -> 2 -> 4
• l2: 1 -> 3 -> 4

合并后的链表应该是：

• 1 -> 1 -> 2 -> 3 -> 4 -> 4

注意，合并后的链表可能包含重复的元素，并且保持有序。

注意事项

• 合并过程中，我们使用了一个哨兵节点（dummy node）来简化边界条件的处理。哨兵节点的next属性将指向合并后链表的头节点。
• 在遍历过程中，我们只需要关注当前节点的值，并根据比较结果将较小的节点添加到结果链表中。
• 当一个链表遍历完成后，我们直接将另一个链表的剩余部分连接到结果链表的末尾，因为这部分已经是有序的，无需进一步处理。

版权：印客学院，仅学习使用 

 

括号生成

JS算法数字n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的 括号组合。

为了生成所有可能的并且有效的括号组合，我们可以采用回溯法（backtracking）来解决这个问题。回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来撤销上一步，即“回溯”，并尝试另一种可能的候选解。

具体到这个问题，我们需要保持左括号的数量总是大于等于右括号的数量，以确保生成的括号序列是有效的。

下面是一个使用JavaScript编写的示例代码：

const generateParenthesis = function(n) {  const result = [];  // 辅助函数，用于生成括号  // left表示剩余的左括号数量，right表示剩余的右括号数量  const backtrack = (str, left, right) => {  // 如果左括号和右括号都已经用完，则将当前组合添加到结果数组中  if (left === 0 && right === 0) {  result.push(str);  return;  }  // 如果左括号还有剩余，则可以添加一个左括号  if (left > 0) {  backtrack(str + '(', left - 1, right);  }  // 只有在剩余的右括号数量大于左括号数量时，才能添加右括号  // 这是为了保证左括号总是先于右括号被使用  if (right > left) {  backtrack(str + ')', left, right - 1);  }  };  // 初始调用回溯函数  backtrack('', n, n);  return result;  
};  // 示例  
console.log(generateParenthesis(3));  
// 输出:  
// [  
//   "((()))",  
//   "(()())",  
//   "(())()",  
//   "()(())",  
//   "()()()"  
// ]

 在这个示例中，generateParenthesis函数是主函数，它接受一个参数n，表示要生成的括号对数。函数内部定义了一个result数组用于存储所有有效的括号组合。然后，它调用了一个辅助函数backtrack，该函数采用回溯法来生成所有可能的括号组合。backtrack函数接收当前已生成的括号字符串str、剩余的左括号数量left和剩余的右括号数量right作为参数。通过递归调用backtrack函数，并在每一步尝试添加左括号或右括号（如果满足条件），我们可以遍历所有可能的括号组合，并将有效的组合添加到result数组中。最后，generateParenthesis函数返回result数组，即所有有效的括号组合。