JZ13 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部
分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变
解题思路
额外空间辅助,使用队列
代码
JZ14 链表中倒数第k个节点
题目描述
输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
解题思路
双指针,快指针先走k-1步,再和慢指针同步走,快指针走到链表尾部则,慢指针指向倒数第k个
代码
//时间复杂度 O(n), 空间复杂度 O(n)
public class Solution {
public int[] reOrderArray (int[] array) {
Queue<Integer> ji = new LinkedList();
Queue<Integer> ou = new LinkedList();
for(int i = 0;i<array.length;i++){
if(array[i] % 2 == 1){
ji.offer(array[i]);
}else {
ou.offer(array[i]);
}
}
int i = 0;
while(!ji.isEmpty()){
array[i++] = ji.poll();
}
while(!ou.isEmpty()){
array[i++] = ou.poll();
}
return array;
}
}
//时间复杂度: O(n), 空间复杂度: O(1)
public class Solution {
public ListNode FindKthToTail (ListNode pHead, int k) {
if(pHead == null)
return pHead;
if(k <= 0)