Java日记2018-05-31

21. 调整数组顺序使奇数位于偶数前面
    数组克隆后计算奇数个数，然后挨个往上添加

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);
        }
    }

22. 链表中倒数第 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;
    }

23. 链表中环的入口结点

使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点，假设到环入口距离x，当相遇时fast移动x+mn,m是圈数，n是环长度，slow移动x+k，k是环内移动数。又因为fast=2slow，那么x+k=m*n.代表x+k等于在环内走m圈，于是让fast指向头结点移动，当再次相遇就是环入口
具体实现不想写了，全是数学，甚至在小学奥数题看到了这个东西

24. 反转链表
    小坑在注释

//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;
    }

25. 合并两个排序的链表

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;
    }
}