链表重排

题目

给定一个奇数位升序，偶数位降序的单链表，编写一个函数，将其按照升序进行排序

注：假定链表第一个元素编号为1、第二个元素编号为2，依次类推；“奇数位”指的是编号为奇数的元素。

示例1:

给定链表 1->8->3->6->5->4->7->2->NULL, 
重新排列为 1->2->3->4->5->6->7->8->NULL

解法

先把链表按照奇数位和偶数位进行拆分，然后对偶数位的链表进行翻转得到两个升序链表。最后对两个升序链表进行归并排序即可。

public class Solution {

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 将链表按奇数位和偶数位进行拆分
        ListNode head2 = head.next;
        ListNode tmp1 = head;
        ListNode tmp2 = head2;
        while (tmp1 != null || tmp2 != null) {
            if (tmp1 != null) {
                tmp1.next = tmp1.next == null ? null : tmp1.next.next;
                tmp1 = tmp1.next;
            }
            if (tmp2 != null) {
                tmp2.next = tmp2.next == null ? null : tmp2.next.next;
                tmp2 = tmp2.next;
            }
        }
        // 翻转偶数位链表
        head2 = reverse(head2);
        // 合并两个链表
        return merge(head, head2);
    }

    /**
     * 翻转链表
     *
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode next;
        pre.next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 升序合并链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode merge(ListNode head1, ListNode head2) {
        if (head1.val > head2.val) {
            ListNode tmp = head1;
            head1 = head2;
            head2 = tmp;
        }
        ListNode head = head1;
        ListNode cur = head1;
        head1 = head1.next;
        // 升序合并
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if (head1 != null) {
            cur.next = head1;
        }
        if (head2 != null) {
            cur.next = head2;
        }
        return head;
    }
}