摘要：拆分鏈表，將和進行拆分，保證原始鏈表不受影響。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。輸入一個字符串長度不超過可能有字符重復(fù)字符只包括大小寫字母。遞歸，記錄一個當(dāng)前節(jié)點的位置，該位置指向最后一個節(jié)點時記錄一次排列。

輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值，以及兩個指針，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用）

拆分成三步

1.復(fù)制一份鏈表放在前一個節(jié)點后面，即根據(jù)原始鏈表的每個節(jié)點N創(chuàng)建N,把N直接放在N的next位置，讓復(fù)制后的鏈表和原始鏈表組成新的鏈表。

2.給復(fù)制的鏈表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;
    }

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。

1.排序的雙向鏈表-中序遍歷二叉樹

2.記錄鏈表的最后一個節(jié)點

3.每次遍歷：設(shè)置樹節(jié)點的left和鏈表的right進行鏈接，鏈接成功后當(dāng)前節(jié)點成為鏈表的末尾節(jié)點，并返回。

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

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

輸入一個字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。

1.把字符串分成兩部分，第一個字符和后面的字符
2.整個字符串的全排列等于：第一個字符+后面字符的全排列，第一個字符和后面的字符諸葛交換。

第一個字符+后面字符的全排列3.除了第一個字符其他字符的全排列等于：第二個字符+后面字符的全排列。

3.遞歸，記錄一個當(dāng)前節(jié)點的位置，該位置指向最后一個節(jié)點時記錄一次排列。

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