<剑指offer> 剑指offer 21、22、24

摘要：
21. 调整数组顺序使奇数位于偶数前面
22. 链表中倒数第k个节点
24. 反转链表

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

题目

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

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

思路

使用双指针方法，将左右的错位数字交换位置，在交换之前判定i，j指向的数字均是错位数字（即为i指向偶数，j指向奇数时方可交换），否则挪动指针。
判定结束条件为i<j；

知识点： x&1 位运算 等价x%2 取余运算，即皆可用于判断数字奇偶性。

代码

class Solution {
    public int[] exchange(int[] nums) {
    	//方法一使用if判断和continue
        // int l=nums.length;
        // int i=0,j=l-1;
        // int tem=0;
        // while(i<j){
        //     if(nums[i]%2==1){
        //         i++;
        //         continue;
        //     }
        //     if(nums[j]%2==0){
        //         j--;
        //         continue;
        //     }
        //     tem=nums[i];
        //     nums[i]=nums[j];
        //     nums[j]=tem;
        // }
        // return nums;
        //方法二：直接在循环内将指针位置调整正确
        int i = 0, j = nums.length - 1, tmp;
        while(i < j) {
            while(i < j && (nums[i] & 1) == 1) i++;
            while(i < j && (nums[j] & 1) == 0) j--;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        i,j=0,len(nums)-1
        while i<j:
            # x&1 位运算 等价x%2 取余运算，即皆可用于判断数字奇偶性。
            while i < j and nums[i] & 1 == 1: i += 1
            while i < j and nums[j] & 1 == 0: j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        return nums

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

题目

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

示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

思路

使用双指针方法可以不用变例链表获得最终的节点；
双指针i j均指向第一个节点，然后将指针i前移k个节点，然后将ij之间保持这个距离共同向前平移，等i指针指向null时，j指针指向的位置节点即是最终的结果。

/**
 * 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) {
        ListNode i=head,j=head;
        int count=0;
        while(count<k){
            i=i.next;
            count++;
        }
        while(i!=null){
            i=i.next;
            j=j.next;
        }
        return j;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        i,j=head,head
        count=0
        while count<k:
            i=i.next
            count+=1
        while i!=None:
            i=i.next
            j=j.next
        return j

剑指 Offer 24. 反转链表

题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 双指针法：
        // ListNode pre=null;
        // ListNode cur=head,temp=head;
        // while(cur!=null){
        //     temp=cur.next;
        //     cur.next=pre;
        //     pre=cur;
        //     cur=temp;
        // }
        // return pre;
        // 递归法：
        //其中head==null是为了防止链表仅有一个节点的特殊情况
        if(head==null||head.next==null){
            return head;
        }
        //获取下一个节点
        ListNode ret=reverseList(head.next);
        //其中head.next与ret指的节点是同一个
        head.next.next=head;
        //将head的下一个节点指向Null，不断递归直到第一个节点的下一个节点也指向NUll
        head.next=null;
        return ret;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 递归法
        if head == None or head.next==None:
            return head
        ret=self.reverseList(head.next)
        head.next.next=head
        head.next=None
        return ret