剑指Offer No.21-30题解

剑指OFFER 21.调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

解题思路

双指针法，如题意要求奇数位于偶数前，那么一个指针从左边寻找偶数、另一个从右边向左寻找奇数交换即可。

代码

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            while(left < nums.length && nums[left] % 2 != 0){
                left++;
            }
            while(right >= 0 && nums[right] % 2 == 0){
                right--;
            }
            if(left > right){
                break;
            }
            swap(nums,left,right);
        }
        return nums;
    }

    private void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

剑指OFFER 22.链表中倒数第k个节点

题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

解题思路

快慢双指针法，遍历一次即可。由题意倒数第K个节点即正数第N-K个节点（N为链表总节点数），首先设一个指针fast从head遍历至第K个节点，然后加入一指针slow从头遍历，可知fast再走N-K次到头，所以当前面的fast指针为空（遍历完）时slow正好是正数第N-K个节点，即倒数第K个节点。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && k-- > 0){
            fast = fast.next;
        }
        if(k > 0){
            return null;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}