只遍历链表一次的做法： 双指针算法。第一个指针先走k-1步，从第k步开始，第二个指针也开始和第一个指针同步走。两个指针距离保持k-1，第一个指针走到尾节点时，第二个就刚好到了倒数第k个节点上。 class Solution { public: int kthToLast(ListNode* head, int k) { if(head == nul…
剑指offer67题-No14.链表中倒数第k个结点
剑指offer67题-No13.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 解法1： 从头到尾扫描数组，遇到偶数就取出来，把偶数后面的数字往前挪，偶数填在最后面。时间复杂度O(n²)，空间复杂度O(1)。 解法2： 开一个新数组从头到尾扫描，东西存新数组里…
剑指offer67题-No2.替换空格
双指针算法。 朴素思想是顺序查找，查找到了之后再进行移动替换。时间复杂度是O(n²)。 更优秀的O(n)解法是，先遍历一遍，找出空格的个数，进而可以得出替换后的字符串长度，用双指针P1，P2。 P1指向原字符串的最后一位字符，P2指向替换后字符串的最后一位（目前为空）。P1、P2开始从后往前，边移动边复制，直到P1遇到了空格，P2添加%20之后，继…