《剑指offer》分解让复杂问题更简单

迷南。 2022-03-07 07:22 161阅读 0赞

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

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer——复杂链表的复制

![转自leetcode剑指offer][leetcode_offer]转了C++，指针之前学的全忘了，唉~ 大概思路：用map存储val一一与head链表对应的结点的地址

缺乏、安全感/ 2022年11月16日 10:39/ 0 赞/ 153 阅读

相关《剑指offer》刷题笔记（分解让复杂问题简单）：复杂链表的复制

《剑指offer》刷题笔记（分解让复杂问题简单）：复杂链表的复制 -------------------- 转载请注明作者和出处：[http://blog.csd

野性酷女/ 2022年06月06日 11:55/ 0 赞/ 136 阅读

相关《剑指offer》刷题笔记（分解让复杂问题简单）：字符串的排列

《剑指offer》刷题笔记（分解让复杂问题简单）：字符串的排列 -------------------- 转载请注明作者和出处：[http://blog.csdn

爱被打了一巴掌/ 2022年06月05日 07:13/ 0 赞/ 124 阅读

相关《剑指offer》刷题笔记（分解让复杂问题简单）：二叉搜索树与双向链表

《剑指offer》刷题笔记（分解让复杂问题简单）：二叉搜索树与双向链表 -------------------- 转载请注明作者和出处：[http://blog.

比眉伴天荒/ 2022年06月05日 06:24/ 0 赞/ 150 阅读

相关【剑指offer】复杂链表的复制

题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请

悠悠/ 2022年04月16日 00:44/ 0 赞/ 372 阅读

相关【剑指offer】复杂链表的复制

复杂链表的复制题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的hea

不念不忘少年蓝@/ 2022年03月31日 02:12/ 0 赞/ 189 阅读

相关《剑指offer》分解让复杂问题更简单

1.复杂链表的复制输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，

迷南。/ 2022年03月07日 07:22/ 0 赞/ 162 阅读

相关剑指Offer-复杂链表的复制

题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中

太过爱你忘了你带给我的痛/ 2022年02月25日 11:14/ 0 赞/ 184 阅读

相关 [剑指offer]复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中

我不是女神ヾ/ 2021年12月19日 15:27/ 0 赞/ 212 阅读

相关剑指offer：复杂链表的复制

试题：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不

今天药忘吃喽~/ 2021年06月24日 16:09/ 0 赞/ 368 阅读