要求：空间复杂度 O(1) ，时间复杂度 O(n) 。 方法1：新链表合并，抄自牛客题解。比较直观。 class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { auto vhead=new ListNode(-1); //设置一个哨兵指针 ListN…
剑指offer67题-No16.合并两个有序链表
剑指offer67题-No15.反转链表
反转链表的三种方法--面试必考（图例超详细解析，小白一看就会！！！）-CSDN博客 要求：空间复杂度 O(1) ，时间复杂度 O(n) 。 方法1：就地逆置，三指针迭代分不太清头插法和就地逆置的区别，感觉没啥区别。三个指针temp、cur、newCur； ListNode* ReverseList(ListNode* head) { if(head…
剑指offer67题-No14.链表中倒数第k个结点
只遍历链表一次的做法： 双指针算法。第一个指针先走k-1步，从第k步开始，第二个指针也开始和第一个指针同步走。两个指针距离保持k-1，第一个指针走到尾节点时，第二个就刚好到了倒数第k个节点上。 class Solution { public: int kthToLast(ListNode* head, int k) { if(head == nul…
剑指offer67题-No13.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 解法1： 从头到尾扫描数组，遇到偶数就取出来，把偶数后面的数字往前挪，偶数填在最后面。时间复杂度O(n²)，空间复杂度O(1)。 解法2： 开一个新数组从头到尾扫描，东西存新数组里…
剑指offer67题-No12.数值的整数次方
要注意正负号。 快速幂算法。算法学习笔记(4)：快速幂 - 知乎 递归快速幂：计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。这个算法的时间复杂度是O(logn)的。 int qpow(int a, int n) { if (n == 0) …
剑指offer67题-No11.二进制中1的个数
可以用移位运算来写，这样的问题在于，负数，c++中的右移是算数右移，（高位补 1），而不是逻辑右移（高位补 0）。n永远不会变成 0，而是会一直保持 -1。 // 错误的示例 int NumberOf1(int n) { // write code here int cnt = 0; while(n != 0){ if((n & 0x1) …
剑指offer67题-No7-No10.简单dp递归合集
NO7斐波那契数列 用递归的写法，复杂度将是O(2^n)级别的，无法忍受。 用三个变量存储递归的中间值，时间复杂度能到O(n)。 public int Fibonacci (int n) { // write code here int t1 = 1; int t2 = 1; int t3 =…
剑指offer67题-No6.旋转数组中的最小数字
二分法。 二分法的本质、模板、例题 - 知乎 二分法的关键是找出目标点的性质。 观察题目中，旋转数组的性质，能发现最小的数字一定是小于等于最右端点的。即找出某区间的最左值，用二分法的右区间模板。 class Solution { public: int minArray(vector<int> &numbers) { int pivo…