剑指Offer Day6 2020-02-24

1.调整数组顺序使奇数位于偶数前面

题目:
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public class Solution {
    public void reOrderArray(int [] array) {
        if (array.length == 0) {
            return;
        }
        int p1 = 0;
        int p2 = array.length - 1;
        while (p1 < p2) {
            while (p1 < p2 && isOdd(array[p1])) {
                p1 ++;
            }
            while (p1 < p2 && !(isOdd(array[p2]))) {
                p2 --;
            }
            if (p1 < p2) {
                int temp = array[p1];
                array[p1] = array[p2];
                array[p2] = temp;
            }
        }
    }
    
    private static boolean isOdd(int num) {
        return (num & 0x1) == 1;
    }
}

2.返回链表倒数第k个结点

题目:
输入一个链表，输出该链表中倒数第k个结点。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        // p1 -> k - 1
        if (head == null || k == 0) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < (k - 1); i ++) {
            if (p1.next != null) {
                p1 = p1.next;
            } else {
                return null;
            }
        }
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}