共计 2301 个字符，预计需要花费 6 分钟才能阅读完成。
1. 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用）
思路
拆分成三步
1. 复制一份链表放在前一个节点后面，即根据原始链表的每个节点 N 创建 N, 把 N 直接放在 N 的 next 位置，让复制后的链表和原始链表组成新的链表。
2. 给复制的链表 random 赋值，即 N`.random=N.random.next。
3. 拆分链表，将 N` 和 N 进行拆分，保证原始链表不受影响。
代码
function Clone(pHead) {
if (pHead === null) {
return null;
}
cloneNodes(pHead);
cloneRandom(pHead);
return reconnetNodes(pHead);
}
function cloneNodes(pHead) {
var current = pHead;
while (current) {
var cloneNode = {
label: current.label,
next: current.next
};
current.next = cloneNode;
current = cloneNode.next;
}
}
function cloneRandom(pHead) {
var current = pHead;
while (current) {
var cloneNode = current.next;
if (current.random) {
cloneNode.random = current.random.next;
} else {
cloneNode.random = null;
}
current = cloneNode.next;
}
}
function reconnetNodes(pHead) {
var cloneHead = pHead.next;
var cloneNode = pHead.next;
var current = pHead;
while (current) {
current.next = cloneNode.next;
current = cloneNode.next;
if (current) {
cloneNode.next = current.next;
cloneNode = current.next;
} else {
cloneNode.next = null;
}
}
return cloneHead;
}
2. 二叉搜索树转换为双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路
1. 排序的双向链表 - 中序遍历二叉树
2. 记录链表的最后一个节点
3. 每次遍历：设置树节点的 left 和链表的 right 进行链接，链接成功后当前节点成为链表的末尾节点，并返回。
代码
function Convert(pRootOfTree) {
var lastNode = null;
lastNode = convertToList(pRootOfTree, lastNode);
while (lastNode && lastNode.left) {
lastNode = lastNode.left;
}
return lastNode;
}
function convertToList(treeNode, lastNode) {
if (!treeNode) {
return null;
}
if (treeNode.left) {
lastNode = convertToList(treeNode.left, lastNode);
}
treeNode.left = lastNode;
if (lastNode) {
lastNode.right = treeNode;
}
lastNode = treeNode;
if (treeNode.right) {
lastNode = convertToList(treeNode.right, lastNode);
}
return lastNode;
}
3. 字符串的排列
输入一个字符串, 按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc, 则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba。
输入一个字符串, 长度不超过 9(可能有字符重复), 字符只包括大小写字母。
思路
1. 把字符串分成两部分，第一个字符和后面的字符 2. 整个字符串的全排列等于：第一个字符 + 后面字符的全排列，第一个字符和后面的字符诸葛交换。
第一个字符 + 后面字符的全排列 3. 除了第一个字符其他字符的全排列等于：第二个字符 + 后面字符的全排列。
3. 递归，记录一个当前节点的位置，该位置指向最后一个节点时记录一次排列。
代码
function Permutation(str) {
var result = [];
if (!str) {
return result;
}
var array = str.split(”);
permutate(array, 0, result);
result.sort();
return [… new Set(result)];
}
function permutate(array, index, result) {
if (array.length – 1 === index) {
result.push(array.join(”));
}
for (let i = index; i < array.length; i++) {
swap(array, index, i);
permutate(array, index + 1, result);
swap(array, i, index);
}
}
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
