- 调整数组顺序使奇数位于偶数前面
数组克隆后计算奇数个数，然后挨个往上添加
public static void reorder(int[] arr) {
int oddcnt = 0;
int i, j;
for (int num : arr) {
if (num % 2 == 1) {
oddcnt++;
}
}
i = 0;
j = oddcnt;
int[] clonearr = arr.clone();
for (int num : clonearr) {
if (num % 2 == 1) {
arr[i] = num;
i++;
} else {
//System.out.println(j);
arr[j] = num;
j++;
}
}
for (int num : arr) {
System.out.println(num);
}
}
- 链表中倒数第 K 个结点
两个指针顺序往下走k
//22. 链表中倒数第 K 个结点
public static ListNode FindKthToTail(ListNode head, int k) {
if(head==null) return null;
ListNode slow,fast;
fast = slow = head;
while(fast!=null && k-->0){
fast=fast.next;
}
System.out.println("fast:"+fast.val);
//k大于0说明链表长度小于k
if(k>0) return null;
//以fast是否为空作为判断，实际上fast最后会是null，null也就是最后一个点的next点；
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
return slow;
}
- 链表中环的入口结点
使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点，假设到环入口距离x，当相遇时fast移动x+mn,m是圈数，n是环长度，slow移动x+k，k是环内移动数。又因为fast=2slow，那么x+k=m*n.代表x+k等于在环内走m圈，于是让fast指向头结点移动，当再次相遇就是环入口
具体实现不想写了，全是数学，甚至在小学奥数题看到了这个东西
- 反转链表
小坑在注释
//24. 反转链表
public static ListNode reverseList(ListNode head) {
if(head==null) return null;
ListNode pre;
ListNode cur;
ListNode next;
pre = null;
cur=head;
while(cur.next!=null) {
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
//走到最后一步时候，记得把最后的链表反转
cur.next=pre;
return cur;
}
- 合并两个排序的链表
public ListNode Merge(ListNode list1, ListNode list2) {
if (list1 == null)
return list2;
if (list2 == null)
return list1;
if (list1.val <= list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
