反转题库

题一、反转链表

方案A、递归

方式一: 头递归法

思路: 核心思想就是从当前链表的头结点开始，依次向后遍历。遍历过程依次改变各节点的 next 指向，即另其指向前一个节点。

过程:

head -> head.next 这两个节点反转时： head.next.next=head; head.next=null 就好了 , 但是如果直接改变节点.next , 那么会找不到下一个节点，所以，进行下面的操作。
通过 next 保存 节点.next 
通过 prev 保存 节点的上一个节点
反转的关键就是将节点的 next 指向 prev

实现

function reverseList(head){
    const reverse = (prev,current)=>{
        if(!current){
            return prev;
        }
        let next = current.next;
        current.next = prev;
        return reverse(current,next);
    }
    return reverse(null,head);
}

方式二: 尾递归法

思路: 核心思想是从当前链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的 next 指向，即另其指向前一个节点。

过程:

head -> head.next 这两个节点反转时： head.next.next=head; head.next=null 就好了
但是如果直接改变了 head.next.next ，那么找不到下一个节点了，所以通过从后往前的方式
从后往前的方式采用递归找到最后一个节点

实现:

function reverseList(head){
    const reverse = (current)=>{
        if(!current || !current.next){
            return current;
        }
        let prev = reverse(current.next);
        current.next.next = current;
        current.next = null;
        return prev;
    }
    return reverse(head);
}

方案B、迭代

方式一: 三指针迭代法

思路: 核心思想就是从当前链表的头结点开始，依次向后遍历。遍历过程依次改变各节点的 next 指向，即另其指向前一个节点。
过程:

通过一个变量保存 next : 由于链表的特性，如果直接将节点的 next 改变为上一个节点，那么下一个节点就无法找到了，所以需要通过一个变量来保存节点的 next 指向，然后改变节点的 next 指向

通过一个变量保存 prev : 由于链表的特性，每一个节点只知道自己的下一个节点，不知道自己的上一个节点，所以需要一个变量来保存当前节点的上一个节点

实现:

function reverseList(head){
    if(!head || !head.next){
        return head;
    }
    let prev = null;
    let next = null;
    let current = head;
    while(current){
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

方式二:双指针迭代法-头插法

思路: 基于三指针迭代法，将头指针充当 next 指针即可

实现:

function reverseList(head){
    if(!head || !head.next){
        return head;
    }
    let prev = null;
    let current = null;
    while(head){
        current = head;
        head = head.next;
        current.next = prev;
        prev = current;
    }
    return prev;
}

方式三: 双指针法-就地逆置法

思路: 基于三指针迭代法，将头指针充当 prev 即可

实现:

function reverseList(head){
    if(!head || !head.next){
        return head;
    }
    let next = head.next;
    let current = head;
    while(next){
        current.next = next.next;
        next.next = head;
        head = next;
        next = current.next;
    }
    return head;
}

题二、链表内指定区间反转

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

方案A、两次遍历【穿针引线】

思路

找到left所在节点的前驱节点precursor,找到right所在节点rightNode,后继节点为successor
以[leftNode,rightNode]为区间进行反转-反转方法随意
拼接反转结果-precursor拼接反转之后链表的头结点,反转之后链表的尾节点拼接successor

实现

function reverseList(head){
  if(!head || !head.next){
    return head;
  }
  let next = head.next;
  let current = head;
  while(next){
    current.next = next.next;
    next.next = head;
    head = next;
    next = current.next;
  }
}
function reverseBetween(head,left,right){
  const dummyNode = new ListNode(-1);
  dummyNode.next = head;
  let precursor = dummyNode;
  for(let i=0;i<left-1;i++){
    precursor = precursor.next;
  }
  let rightNode = precursor;
  for(let i=0;i<right-left+1;i++){
    rightNode = rightNode.next;
  }
  let leftNode = precursor.next;
  let successor = rightNode.next;
  precursor.next = null;
  rightNode.next = null;
  reverseList(leftNode);
  precursor.next = rightNode;
  leftNode.next = successor;
  return dummyNode.next;
}

方案B、一次遍历【穿针引线】

思路: 在待反转的区间里，每次遍历到一个节点，让这个节点来到反转的起始部分。

找到待反转区间起始节点的前驱结点precursor,current 指向待反转区间的起始节点precursor.next
next 节点永远指向current的下一个节点

实现

function reverseBetween(head,left,right){
    let dummyNode =  new ListNode(-1);
    dummyNode.next = head;
    let precursor = dummyNode;
    for(let i=0; i<left-1; i++){
        precursor = precursor.next;
    }
    let next = null;
    let current = precursor.next;
    for(let i=0; i<right-left; i++){
        next = current.next;
        current.next = next.next;
        next.next = precursor.next;
        precursor.next = next;
    }
    return dummyNode.next;
}

题三、K 个一组翻转链表

给你链表的头节点 head,每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

方案A 模拟

function reverse(head, tail) {
  let prev = tail.next;
  let current = head;
  while (prev !== tail) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return [tail, head];
}
function reverseKGroup(head, k) {
  const dummyHead = new ListNode(0);
  dummyHead.next = head;
  let prev = dummyHead;
  while (head) {
    let tail = prev;
    for (let i = 0; i < k; i++) {
      tail = tail.next;
      if (!tail) {
        return dummyHead.next;
      }
    }
    const next = tail.next;
    [head, tail] = reverse(head, tail);
    prev.next = head;
    tail.next = next;
    prev = tail;
    head = tail.next;
  }
  return dummyHead.next;
}

反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。

示例1:

输入：s = "hello"
输出："holle"

示例2:

输入：s = "leetcode"
输出："leotcede"

方案A 双指针-对撞指针

思路: 使用两个指针 i 和 j 对字符串相向地进行遍历。

指针 i 初始时指向字符串 s 的首位，指针 j 初始时指向字符串 s 的末位。在遍历的过程中，我们不停地将 i 向右移动，直到 i 指向一个元音字母（或者超出字符串的边界范围）；同时，我们不停地将 j 向左移动，直到 j 指向一个元音字母。此时，如果 i<j，那么我们交换 i 和 j 指向的元音字母，否则说明所有的元音字母均已遍历过，就可以退出遍历的过程。

function isVowel(ch){
    return "aeiouAEIOU".indexOf(ch) != -1;
}
function reverseVowels(s) {
    let left=0;
    let right=s.length-1;
    let sNums=s.split('');
    while(left<right){
        while(left<right&&!isVowel(sNums[left])){
            left++
        }
        while(left<right&&!isVowel(sNums[right])){
            right--;
        }
        if(left<right){
            [sNums[left],sNums[right]]=[sNums[right],sNums[left]];
            left++;
            right--;
        }
    }
    return sNums.join('');
};

反转字符串里的单词I

方案A 通过API

思路: 很多语言对字符串提供了 split（拆分），reverse（翻转）和 join（连接）等方法，因此我们可以简单的调用内置的 API 完成操作：

使用 split 将字符串按空格分割成字符串数组；
使用 reverse 将字符串数组进行反转；
使用 join 方法将字符串数组拼成一个字符串。

function reverseWord(s){
    return s.trim().split(/\s+/).reverse().join(' ');
}

// const s="the sky is blue";
const s="a good   example"
console.log(reverseWord(s));  

方案B 双端队列

思路: 由于双端队列支持从队列头部插入的方法，因此我们可以沿着字符串一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可。

定义双指针
- left：字符串头部
- right：字符串尾部
去除字符串开头空白字符
去除字符串结尾空白字符
依次进行拼接单词操作

function reverseWord(s){
    let len=s.length;
    let left=0;
    let right=len-1;
    while(left<=right&&s[left]==' '){
        left++
    } 
    while(left<=right&&s[right]==' '){
        right--
    }
    let result=[];
    let word='';
    while(left<=right){
        if(word.length&&s[left]==' '){
            result.unshift(word);
            word='';
        }else if(s[left]!=' '){
            word+=s[left];
        }
        left++
    }
    result.unshift(word);
    return result.join(' ');
}

const s="the sky is blue";
// const s="a good   example"
console.log(reverseWord(s)); 

性能分析:

时间复杂度：O(n)，其中 nn 为输入字符串的长度。

空间复杂度：O(n)，双端队列存储单词需要 O(n) 的空间。

反转字符串里的单词II

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例:

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

方案A 开辟额外空间

思路:开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。

遍历字符串
获取字符串里的单词
- 记录单词的起始位置
- 记录单词的截止位置（遍历到空格的时候）
- 将遍历到的单词逆序添加到额外空间
遍历空格
将额外空间通过空格拼接起来

function reverse1(s){
    const result=[];
    const len=s.length;
    let i=0;
    while(i<len){
    let start=i;
    while(i<len&&s[i]!=' '){
        i++
    }
    for(let p=start;p<i;p++){
        result.push(s.charAt(start+i-1-p));
    }
    while(i<len&&s.charAt(i)==' '){
        i++;
        result.push(' ');
    }
    }
    return result.join('');
}

const s="Let's take LeetCode contest";
console.log(reverse1(s));

性能分析:

时间复杂度：O(N)，其中 N 为字符串的长度。原字符串中的每个字符都会在 O(1) 的时间内放入新字符串中。

空间复杂度：O(N)。我们开辟了与原字符串等大的空间。

题一、反转链表​

方案A、递归​

方案B、迭代​

题二、链表内指定区间反转​

方案A、两次遍历【穿针引线】​

方案B、一次遍历【穿针引线】​

题三、K 个一组翻转链表​

方案A 模拟​

反转字符串中的元音字母​

方案A 双指针-对撞指针​

反转字符串里的单词I​

方案A 通过API​

方案B 双端队列​

反转字符串里的单词II​

方案A 开辟额外空间​