java">import java.util.ArrayList;
import java.util.List;

/**
 * 奇数节点升序、偶数节点降序，得到整体升序的链表
 */
public class OddEvenLink {

    private static class Node {
        int value = -1;

        Node next = null;

        public Node(){
        }

        public Node(int value){
            this.value = value;
        }
    }

    public static void main(String[] args) {
        OddEvenLink oddEvenLink = new OddEvenLink();
        // 升序
        int[] oddNodeValues = {1, 6, 10, 60};
        // 降序
        int[] evenNodeValues = {100, 11, 5, 4};
        // 构建原始链表
        Node oldHeadNode = oddEvenLink.getOldLink(oddNodeValues, evenNodeValues);
        // 处理原始链表，得到新链表
        Node newHeadNode = oddEvenLink.getNewLink(oldHeadNode);
        // 遍历新链表
        oddEvenLink.searchNewLink(newHeadNode);
    }

    public Node getOldLink(int[] oddNodeValues, int[] evenNodeValues){
        int i = 0;
        int j = 0;
        Node dummyHeadNode = new Node();
        Node currentNode = dummyHeadNode;
        boolean isCurrentOdd = true;
        while(i < oddNodeValues.length || j < evenNodeValues.length){
            Node node;
            if(isCurrentOdd){
                node = new Node(oddNodeValues[i++]);
            } else {
                node = new Node(evenNodeValues[j++]);
            }

            currentNode.next = node;
            currentNode = node;
            isCurrentOdd = !isCurrentOdd;
        }

        return dummyHeadNode.next;
    }

    public Node getNewLink(Node oldHeadNode){
        // 分离奇数和偶数链表
        List<Node> oddHeadNoeAndEvenHeadNode = getOddLinkAndEvenLink(oldHeadNode);
        Node oldOddHeadNode = oddHeadNoeAndEvenHeadNode.get(0);
        Node oldEvenHeadNode = oddHeadNoeAndEvenHeadNode.get(1);
        // 反转偶数链表
        Node newEvenHeadNode = getNewEvenLink(oldEvenHeadNode);
        // 合并奇数链表和新的偶数链表
        return getNewLink(oldOddHeadNode, newEvenHeadNode);
    }

    public void searchNewLink(Node newHeadNode){
        Node currentNode = newHeadNode;
        while(currentNode != null){
            System.out.println(currentNode.value);
            currentNode = currentNode.next;
        }
    }

    private Node getNewLink(Node oldOddHeadNode, Node newEvenHeadNode){
        Node currentOddNode = oldOddHeadNode;
        Node currentEvenNode = newEvenHeadNode;
        Node dummyNewHeadNode = new Node();
        Node currentNewNode = dummyNewHeadNode;
        while(currentOddNode != null && currentEvenNode != null){
            if(currentOddNode.value <= currentEvenNode.value){
                currentNewNode.next = currentOddNode;
                currentOddNode = currentOddNode.next;
            } else {
                currentNewNode.next = currentEvenNode;
                currentEvenNode = currentEvenNode.next;
            }

            currentNewNode = currentNewNode.next;
        }

        if(currentOddNode == null && currentEvenNode == null){
            return dummyNewHeadNode.next;
        }

        if(currentOddNode != null){
            currentNewNode.next = currentOddNode;
        }

        if(currentEvenNode != null){
            currentNewNode.next = currentEvenNode;
        }

        return dummyNewHeadNode.next;
    }

    private Node getNewEvenLink(Node oldEvenHeadNode){
        Node currentNode = oldEvenHeadNode;
        Node currentPreNode = null;
        while(currentNode != null){
            Node currentNextNode = currentNode.next;
            currentNode.next = currentPreNode;
            currentPreNode = currentNode;
            currentNode = currentNextNode;
        }

        return currentPreNode;
    }

    private List<Node> getOddLinkAndEvenLink(Node oldHeadNode){
        // 奇数伪节点
        Node dummyOddHeadNode = new Node();
        Node currentOddNode = dummyOddHeadNode;
        // 偶数伪节点
        Node dummyEvenHeadNode = new Node();
        Node currentEvenNode = dummyEvenHeadNode;
        Node currentNode = oldHeadNode;
        boolean isCurrentOdd = true;
        while(currentNode != null){
            if(isCurrentOdd){
                currentOddNode.next = currentNode;
                currentOddNode = currentOddNode.next;
            } else {
                currentEvenNode.next = currentNode;
                currentEvenNode = currentEvenNode.next;
            }

            currentNode = currentNode.next;
            isCurrentOdd = !isCurrentOdd;
        }

        currentOddNode.next = null;
        currentEvenNode.next = null;

        List<Node> nodes = new ArrayList<>();
        nodes.add(dummyOddHeadNode.next);
        nodes.add(dummyEvenHeadNode.next);
        return nodes;
    }

}