题解 | #反转链表#

本题思路是将奇数的下标节点和偶数下标节点分成两个链表，分别是oddHead，evenHead，然后奇数下标的链表就是升序的，偶数下标的就是降序的，然后我们把偶数下标的链表翻转，那他也是升序的了，这样我们得到了两个升序链表，将他们合并即可。

import java.util.*;

/*
 * 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 sortLinkedList (ListNode head) {
        // write code here
        ListNode oddHead = new ListNode(0);
        ListNode oddPre = oddHead;
        ListNode evenHead = new ListNode(0);
        ListNode evenPre = evenHead;
        int index = 1;
        while(head != null) {
            if(index % 2 != 0) {
                oddHead.next = new ListNode(head.val);
                oddHead = oddHead.next;
            } else {
                evenHead.next = new ListNode(head.val);
                evenHead = evenHead.next;
            }
            head = head.next;
            index++;
        }
        ListNode even = evenPre.next;
        ListNode odd = oddPre.next;
        even = reverseList(even);
        ListNode res = mergeNode(even, odd);
        return res;
    }
    private ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    private ListNode mergeNode(ListNode head1, ListNode head2) {
        if(head1 == null) {
            return head2;
        }
        if(head2 == null) {
            return head1;
        }
        if(head1.val <= head2.val) {
            head1.next = mergeNode(head1.next, head2);
            return head1;
        } else {
            head2.next = mergeNode(head1, head2.next);
            return head2;
        }        
    }
}