【算法】解题总结：剑指Offer 13 调整数组顺序使奇数位于偶数前面、剑指Offer 14 链表中倒数最后k个结点

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

（中等）

题目

描述

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

示例1

输入：

[1,2,3,4]

返回值：

[1,3,2,4]

示例2

输入：

[2,4,6,5,7]

返回值：

[5,7,2,4,6]

思路

我的思路是通过前移部分需要移动的奇数元素，来使得数组中的奇数在数组中的前部分，偶数在后部分，通过遍历数组，如果当前元素为奇数，那么我们需要将它前移到它的前一个数不再是偶数为止，对数组中所有奇数都这样做，最终偶数的顺序也会自然排好。

实现

public class JZ13调整数组顺序使奇数位于偶数前面 {
    public int[] reOrderArray(int[] array) {
        if (array == null) {
            return null;
        }

        int[] tmp = new int[array.length];
        System.arraycopy(array, 0, tmp, 0, tmp.length);

        for (int i = 1; i < tmp.length; i++) {
            if (isOdd(tmp[i])) { //当前为奇数
                int j = i; //记录下当前下标
                while (j >= 1 && !(isOdd(tmp[j - 1]))) { //若前一个数为偶数，则一直前移到前一个数为奇数为止
                    swap(tmp, j - 1, j);
                    j--;
                }
            }
        }
        return tmp;
    }

    /**
     * 交换数组中的两个元素的位置
     *
     * @param array
     * @param i
     * @param j
     */
    public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 是否为奇数
     *
     * @param x
     * @return
     */
    public boolean isOdd(int x) {
        if (x % 2 != 0) {
            return true;
        }
        return false;
    }
}      

之所以运行时间偏低是因为我在之后复盘其他人的题解时，发现他们基本都是用的两数组拼接的方法做的，即遍历一遍数组，奇数元素添加到预创建的一个奇数数组中（或是链表），偶数则同理，最终将奇偶两个数组或链表拼接起来返回，虽然他们这种方法很快，用空间换取了时间，但我认为这种方法锻炼不到思维，没什么意思，因此我更偏向于用我这种交换法去做，当然这只是站在平时锻炼编码能力的角度出发的。

JZ14 链表中倒数最后k个结点

（中等）

题目

描述

输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

示例1

输入：

{1,2,3,4,5},1

返回值：

{5}

思路

这是一道非常经典的题目，思路十分易懂，我们先创建一个先行结点标志位，即 frontNode，先让这个标制结点向后走 k - 1 次，之后再让指向第一个结点的 nowNode 和 当前指向第 k 个结点的 frontNode 同时后移，到 frontNode 指向最后一个结点即可终止，此时，nowNode 由于一直和 frontNode 保持 k 个单位的距离，因此最终它自然也就指向了倒数第 k 个结点。

（另外，我的吐槽：官方给的注释真实太zz了，最起码要说一下这个 pHead 是头指针的意思还是头结点的意思吧，那可偏差一个结点单位的距离呢，这里解释个 ListNode 类简直是多此一举。）

实现

public class JZ14链表中倒数最后k个结点 {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int size = sizeList(pHead);
        if (k > size || k <= 0) {
            return null;
        }

        ListNode nowNode = pHead;
        ListNode frontNode = nowNode;

        for (int i = 1; i < k; i++) {
            frontNode = frontNode.next;
        }

        while (frontNode.next != null) {
            nowNode = nowNode.next;
            frontNode = frontNode.next;
        }

        return nowNode;
    }

    public int sizeList(ListNode pHead) {
        int num = 0;
        while (pHead != null) {
            num++;
            pHead = pHead.next;
        }
        return num;
    }
}