题解 | #链表的奇偶重排#

import java.util.*;
// 使用递归写法 浪费空间和时间，最好使用节点替换
// 先分奇偶 然后在按照顺序写入ListNode即可
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // 空链表或者只有一个结点
        if(null ==head || null == head.next) {
            return head;
        }

        StringBuilder noEvenNum = new StringBuilder();
        StringBuilder evenNum = new StringBuilder();
        oddEvenList(noEvenNum, evenNum, 0, head);
        // 组装node
        evenNum.append(noEvenNum);
        String[] splitNoEvenNum = evenNum.toString().split(",");
        int a = 0;
        int noVenLen = splitNoEvenNum.length;
        ListNode newListHead = null;
        if (noVenLen > 0) {
            newListHead = new ListNode(Integer.parseInt(splitNoEvenNum[a]));
            if (a + 1 < noVenLen) {
                deal(noVenLen, a, newListHead, splitNoEvenNum);
            }
        }

        return newListHead;
    }

    public static void deal(int venLen, int rem, ListNode head, String[] splitNum) {
        rem++;
        ListNode newListHead = new ListNode(Integer.parseInt(splitNum[rem]));
        head.next = newListHead;
        if (rem + 1 < venLen) {
            deal(venLen, rem, newListHead, splitNum);
        }
    }

    public static void oddEvenList(StringBuilder noEvenNum, StringBuilder evenNum,
                                   int remember, ListNode head) {
        int val = head.val;
        if (remember % 2 == 0) {
            evenNum.append(val).append(",");
        } else {
            noEvenNum.append(val).append(",");
        }
        remember++;
        ListNode next = head.next;
        if (null != next) {
            oddEvenList(noEvenNum, evenNum, remember, next);
        }
    }
}