排序奇升偶降链表

问题描述

• 给定一个奇数位升序，偶数位降序的链表，将其重新排序。

输入： 1->8->3->6->5->4->7->2->NULL
输出： 1->2->3->4->5->6->7->8->NULL

算法分析

1. 按奇偶位置拆分链表，得1->3->5->7->NULL和8->6->4->2->NULL
2. 反转偶链表，得1->3->5->7->NULL和2->4->6->8->NULL
3. 合并两个有序链表，得1->2->3->4->5->6->7->8->NULL

代码实现

public class Solution {

    public static void main(String[] args) {
    }

    public ListNode sortOddEvenList(ListNode root) {
        if (root == null || root.next == null) {
            return root;
        }
        ListNode[] partition = this.partition(root);
        ListNode reverse = reverse(partition[1]);
        return merge(partition[0], reverse);
    }

    public ListNode[] partition(ListNode head) {
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        ListNode odd = head;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = null;
        return new ListNode[]{head, evenHead};
    }

    public ListNode reverse(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (l1 != null) {
            curr.next = l1;
        }
        if (l2 != null) {
            curr.next = l2;
        }
        return dummy.next;
    }
}