头条面试算法题

链表奇数位升序，偶数位降序，如何改为有序链表

package bytedance.linkedlist;

/**
 * @author Galip
 * @version 1.0
 * @date 2020/2/6 11:40
 */
public class OddEvenLinkedList {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(4);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(5);

        printList(oddEvenLinkedList(head));
    }

    private static class Node {
        Node next;
        int val;

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

    private static void printList(Node head) {
        while (head != null) {
            System.out.print(head.val + "->");
            head = head.next;
        }
    }

    public static Node oddEvenLinkedList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        //将偶数链表拆分出来
        Node evenHead = getEvenList(head);
        //逆序偶数链表
        Node reEvenHead = reverseList(evenHead);
        //归并奇偶链表
        Node mHead = mergeList(head, reEvenHead);
        return mHead;
    }

    private static Node getEvenList(Node head) {
        Node cur = head;
        Node next = null;
        Node evenHead = head.next;

        while (cur != null && cur.next != null) {
            next = cur.next;
            cur.next = next.next;
            cur = cur.next;

            next.next = cur.next;
            next = next.next;
        }
        return evenHead;
    }

    private static Node reverseList(Node head) {
        Node pre = null;
        Node cur = head;
        Node next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private static Node mergeList(Node head1, Node head2) {
        Node vHead = new Node(-1);
        Node cur = vHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
                cur = cur.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
                cur = cur.next;
            }
        }
        cur.next = head1 == null ? head2 : head1;
        return vHead.next;
    }


}