删除排序链表中的重复元素 && 翻转二叉树 && 重复的子字符串

删除排序链表中的重复元素

这是力扣 83 题

给定一个已排序的链表的头  head ， 删除所有重复的元素，使每个元素只出现一次 。返回  已排序的链表 。

解题思路

这是一道关于链表的简单题，本来链表系列的题目在之前就结束了，不过这几天在刷题的过程中无意间看到了这题，因此就做起来了。这题不难，而且这道题有很多不同的版本，有的版本会有些难度。在这里我就介绍一下这个简单版本的删除排序链表中的重复元素的题目。

遍历法

根据题意可以知道给定的链表是已经排序的，所以一旦出现重复元素，它们在链表中出现的位置一定是连续的。因此大致思路就出来了，我们只需对链表进行遍历，遇到相同的元素把它删除即可。具体思路如下：

我们首先让指针 cur 指向链表的头节点，然后再开始对链表进行遍历。如果当前的 cur 指针与 cur.next 对应的元素相同，那么我们就将 cur.next 从链表中移除；如果不相同，则代表链表中已经不存在其它与 cur 指针对应的元素的相同的节点，所以可以将 cur 指针指向 cur.next 继续往下遍历移动。当遍历完整个链表之后，最后返回链表的头节点即可。

这是一种非常简单且容易理解的思路，可能一下子会想不到，但是看到思路后又会感觉很容易。大家可以多看看这道题目的思路，快速将它理解透。

相关代码如下：

var deleteDuplicates = function(head) {
    let curr = head;
    while(curr!==null&&curr.next!==null){
        if(curr.val===curr.next.val){
            curr.next=curr.next.next;
        }else{
            curr=curr.next;
        }
    }
    return head;
};

翻转二叉树

这是力扣 226 题

给你一棵二叉树的根节点  root ，翻转这棵二叉树，并返回其根节点。

解题思路

这道题是一道比较简单的经典题，题意明确，容易看懂，看到这道题，我们就应该想到思路，比如递归，迭代等等解法思路。另外，对于二叉树的题目，我的建议是也可以和链表一样在纸上画出来，会更清晰。这道题就是把每一个节点的左右节点翻转一下，就可以达到整体翻转的效果。

递归解法

递归是二叉树中用的最频繁的解法之一。在碰到二叉树相关的题目的时候，我们首先可以想到递归法来解决。但是递归的缺点是比较耗性能，所以在开发中会尽量少用递归。 对于这题，其实就是交换一下左右节点，然后再递归地交换左节点和右节点。

总结递归的两个条件如下：

• 终止条件：当前节点为 null 时返回
• 交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点

相关代码如下：

var invertTree = function(root) {
if (root === null) {
        return null;
    }
    const left = invertTree(root.left);
    const right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

迭代解法

递归能做的事，迭代也能做。对于这题，如果要用迭代法来解决的话，我们首先需要先将根节点放入到队列中，然后不断地迭代队列中的元素。但是我觉得能用递归解法就尽量用递归解法，毕竟递归代码简短，迭代代码繁多。

相关代码如下：

var invertTree = function(root) {
    const invertNode=function(root,left,right){
        let temp=left;
        left=right;
        right=temp;
        root.left=left;
        root.right=right;
    }
    let stack=[];
    if(root===null){
        return root;
    }
    stack.push(root);
    while(stack.length){
        let node=stack.pop();
        if(node!==null){
            node.right&&stack.push(node.right);
            node.left&&stack.push(node.left);
            stack.push(node);
            stack.push(null);
        }else{
            node=stack.pop();
            invertNode(node,node.left,node.right);
        }
    }
    return root;
};

重复的子字符串

这是力扣 459 题

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过 10000。

解题思路

这又是一道有关字符串的题目，难度为中等。在上一篇文章中的一道字符串题目仅仅用一行代码就 KO 了。所以这里也会附上一种代码较短的方法供大家参考。接下来就来介绍几种关于此题的解题思路。

暴力解法

暴力解法也算是我文章中的常客了，毕竟遇题不会就考虑暴力，暴力能解决 70% 的题目。对于这道题，思路如下：

• 首先设置 s 的长度 length
• 然后通过 for 循环遍历字符串，并累加字符串
• 再判断是否为重复的长度，如果不存在，则返回 false

相关代码如下：

const repeatedSubstringPattern = (s) => {

  const length = s.length;
  let str = '';
  for (let i = 0; i < s.length - 1; i++) {
    str += s[i];
    if (s === str.repeat(Math.floor(length / str.length))) {
      return true;
    }
  }
  return false;
};

极短解法

相关代码如下：

var repeatedSubstringPattern = function(s) {
    let t = s+s
    t = t.substring(1,t.length-1)
    return t.indexOf(s) == -1? false:true
};

只需三行代码即可。拼接两个 s 字符串，去除前后两个字符之后仍然能出现字符串 s即为 true。如果能想到这种思路解起来就很容易，没想到的话那就可以考虑用暴力解法解君愁了。

滑动窗口

这是第二次在文章中提到滑动窗口了，滑动窗口也是非常经典的解法了。对于滑动窗口，感兴趣的朋友可以看看我之前的力扣刷题，里面有提及过此解法。

思路大致和暴力解法差不多。设置窗口的宽度，并重复。同时更新子字符串，不断循环，直到满足边界条件即可，若不满足，返回 false。

相关代码如下：

var repeatedSubstringPattern = function(s) {
    let len = s.length;
    let step = 1;
    let initStr = s.substring(0, step);
    while(step <= len / 2) {
        if(initStr.repeat(len / step) === s) {
            return true;
        }
        step++;
        initStr = s.substring(0, step);
    }
    return false;
};