算法test004

一个链表：奇数序号升序，偶数序号降序，要求做这个链表的整体升序排序。
例子：1 8 3 6 5 4 7 2 9，最后输出1 2 3 4 5 6 7 8 9。
思路：
分成三步
（1）首先根据奇数位和偶数位拆分成两个链表。
（2）然后对偶数链表进行反转。
（3）最后将两个有序链表进行合并。
public class test004 {
public ListNode sort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode evenHead = getEvenHead(head);
return merge(head, reverse(evenHead));
}
private ListNode getEvenHead(ListNode head) {
ListNode cur = head;
ListNode dummyEven = new ListNode(0);
ListNode curEven = dummyEven;
while (cur != null && cur.next != null) {
ListNode next = cur.next;
cur.next = next.next;
next.next = null;
cur = cur.next;

        curEven.next = next;
        curEven = curEven.next;
    }
    return dummyEven.next;
}
private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}
private ListNode merge(ListNode one, ListNode two) {
    ListNode dummyHead = new ListNode(0);
    ListNode cur = dummyHead;
    while (one != null && two != null) {
        if (one.val < two.val) {
            cur.next = one;
            one = one.next;
        } else {
            cur.next = two;
            two = two.next;
        }
        cur = cur.next;
    }
    cur.next = one == null ? two : one;
    return dummyHead.next;
}

}

欢迎交流指正~