链表-奇数位升序偶数位降序-让链表变成升序

public class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(100);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(90);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(1);
        ListNode newHead = sortList(head);
        printList(newHead);
    }
    
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode slow = head, curNode = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = curNode;
            curNode = curNode.next;
            fast = fast.next.next;
        }
        // unlink
        slow.next = null;
        return mergeSort(sortList(head), sortList(curNode));
    }
    
    public static ListNode mergeSort(ListNode h1, ListNode h2) {
        ListNode newHead = new ListNode(-1);
        ListNode moveNode = newHead;
        ListNode tmp;
        while (h1 != null && h2 != null) {
            if (h1.val < h2.val) {
                tmp = new ListNode(h1.val);
                h1 = h1.next;
            } else {
                tmp = new ListNode(h2.val);
                h2 = h2.next;
            }
            moveNode.next = tmp;
            moveNode = moveNode.next;
        }
        if (h1 != null) {
            moveNode.next = h1;
        }
        if (h2 != null) {
            moveNode.next = h2;
        }
        return newHead.next;
    }
    
    private static void printList(ListNode head) {
        String s = "";
        while (head != null) {
            s += head.val + " ";
            head = head.next;
        }
        System.out.println(s);
    }
}

class ListNode {
    ListNode next;
    int val;
    ListNode(int val) {
        this.val = val;
        next = null;
    }
}