调整数组顺序使奇数位于偶数前VS链表奇偶重排

有两种方法：
一是开辟另外的空间：

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> arr;
        for( int v : array){
            if((v & 1)) arr.push_back(v);
        }
        for(int v : array){
            if(!(v & 1)) arr.push_back(v);
        }
        copy(arr.begin(), arr.end(), array.begin());
    }
};

二是利用双指针法：

import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        int len = array.length;
        if(len <= 1)
            return;

        int i = 0;
        while(i < len){
            int j = i + 1;
            if(array[i] % 2 == 0){ //遇到偶数停下来，j前进
                while(array[j] % 2 ==0){
                    if(j == len - 1)
                        return;
                    j++;
                }
                //j遇到了奇数，要做交换了
                int count = j - i;
                int temp = array[i];
                array[i] = array[j];//交换
                //再将数组i 到 j之间的数整体后移
                while(count > 1){
                    array[i+count] = array[i+count-1];
                    count--;
                }
                array[i+1] = temp;
            }
            i++;
        }
    }
}

链表的奇偶重排

画个图就清晰得多了

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head == null || head.next == null)
            return head;

        ListNode jtail = head;
        ListNode ohead = head.next;
        ListNode otail = ohead;



        while(jtail.next != null && otail.next != null){
            jtail.next = otail.next;
            jtail = jtail.next;
            otail.next = jtail.next;
            otail = otail.next;
        }
        jtail.next = ohead;
        return head;
    }
}

变形：对奇升偶降链表进行排序
https://mp.weixin.qq.com/s/377FfqvpY8NwMInhpoDgsw

解题步骤

• 奇偶拆分链表
• 对偶链表进行反转
• 合并两个链表

总的代码：

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head == null || head.next == null)
            return head;

        ListNode jtail = head;
        ListNode ohead = head.next;
        ListNode otail = ohead;


        //拆分奇偶链表
        while(jtail.next != null && otail.next != null){
            jtail.next = otail.next;
            jtail = jtail.next;
            otail.next = jtail.next;
            otail = otail.next;
        }
        //反转偶数链表
        ListNode cur = ohead;
        ListNode pre = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

       //合并两个链表
      ListNode dummy = new ListNode(0);
      cur = dummy;
      while(jhead != null && pre != null){
           if(jhead.val < pre.val){
                cur.next = jhead;
                jhead = jhead.next;
            } else {
                cur.next = pre;
                pre = pre.next;
            }
            cur = cur.next;
      }
      if(jhead != null)
        cur.next = jhead;
      if(pre != null)
        cur.next = pre;

      return dummy.next;
    }
}