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]]; }