算法分析 [反转] 2019-03-11

1. 反转

541. 反转字符串（指定每隔k个值反转，再隔k个值不变，每次都是2k为范围） Reverse String II easy
法1. 时间复杂度O(n)，空间复杂度O(n)
由于每次都是2k，有公式是 mod=x/2，如果mod%2==0，那么x%2的值需要反转，否则只需要对前k个值取反，后续的值不做调整
法2. 时间复杂度O(n)，空间复杂度O(n)
不用公式，直接start取到结尾，每次判断是否达到最后只（自己尝试下）

557. 反转单词 Reverse Words in a String III
法1. 时间复杂度O(n)，空间复杂度O(n)
每个空字符都进行一次双指针反转，最后一个单词没有空字符，要做一次收尾处理

345. 反转字符串中的元音字母 Reverse Vowels of a String easy
法1.双指针 时间复杂度O(n)，空间复杂度O(1)
一个指针p从头开始，一个指针q从尾开始

7. 反转整形 Reverse Integer easy
法1. 时间复杂度O(n)，空间复杂度O(1)
需要考虑越界问题

206. 反转单链表 Reverse Linked List easy
法1. 时间复杂度O(n)，空间复杂度O(1)
使用头指针插入法，设置指针为h=null，每次将遍历到的指针插入到头指针前cur.next=h;h=cur;

92. 指定范围的反转单链表Reverse Linked List II medium
法1. 时间复杂度O(n)，空间复杂度O(1)
双指针，当到达需要反转的位置，使用 slow 和 fast切换，slow永远不改变，永远指向结尾

            slow.next = fast.next;
            fast.next = pre.next;
            pre.next = fast;
            fast = slow.next;