排序奇升偶降链表

题目描述 : 给定一个奇数位升序，偶数位降序的链表，将其重新排序。

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

要求: 时间复杂度为O(N)，空间复杂度O(1)。

思路:

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

代码:

class Solution {
    /**
     * 1. 拆分奇偶链表
     * 2. 翻转偶数链表
     * 3. 合并有序链表
     */
    public static ListNode sortList(ListNode list) {
        // 1. 拆分奇偶链表
        ListNode[] arr = separate(list);
        // 2. 翻转偶数链表
        ListNode oddList = arr[0];
        ListNode evenList = reverse(arr[1]);
        // 3. 合并有序链表
        return mergeSortedLists(oddList, evenList);
    }

    private static ListNode mergeSortedLists(ListNode oddList, ListNode evenList) {
        ListNode dummyNode=new ListNode();
        ListNode cur=dummyNode;
        while(oddList!=null || evenList!=null){
            if(oddList!=null){
                cur.next=oddList;
                oddList=oddList.next;
                cur=cur.next;
                cur.next=null;
            }
            if(evenList!=null){
                cur.next=evenList;
                evenList=evenList.next;
                cur=cur.next;
                cur.next=null;
            }
        }
        return dummyNode.next;
    }

    private static ListNode reverse(ListNode listNode) {
        if(listNode==null || listNode.next==null) return listNode;
        ListNode newHead=reverse(listNode.next);
        listNode.next.next=listNode;
        listNode.next=null;
        return newHead;
    }

    private static ListNode[] separate(ListNode list) {
        if (list == null || list.next == null) return new ListNode[]{list, null};
        ListNode dummyNode = new ListNode();
        ListNode cur = dummyNode;
        ListNode p = list;
        while(p!=null && p.next!=null){
            cur.next=p.next;
            cur=cur.next;
            p.next=p.next.next;
            p=p.next;
            cur.next=null;
        }
        return new ListNode[]{list,dummyNode.next};
    }

    public static void main(String[] args) {
        ListNode listNode = sortList(new ListNode(1, new ListNode(8, new ListNode(3, new ListNode(6, new ListNode(5,
                new ListNode(4, new ListNode(7, new ListNode(2)))))))));
        System.out.println(listNode);
    }
}

感谢大佬 @chenchen4396 提供的优化思路：

• 直接记住第一个和第二个节点的位置，遇到奇数插在头节点后面，偶数插在尾节点前面

class Solution {
    /**
     * 1. 记住前两个节点,奇数尾插,偶数头插
     * 2. 合并有序链表
     */
    public static ListNode sortList(ListNode list) {
        // 1. 链表小于两个节点,直接返回
        if (list == null || list.next == null) return null;
        // 2. 记住前两个节点,奇数尾插,偶数头插
        ListNode oddList = new ListNode(), cur = oddList;
        ListNode evenList = null;
        int i = 1;
        while (list != null) {
            if ((i++) % 2 == 1) {
                cur.next = list;
                cur = cur.next;
                list = list.next;
                cur.next = null;
            } else {
                ListNode next = list.next;
                list.next = evenList;
                evenList = list;
                list = next;
            }
        }
        // 3. 合并有序链表
        return mergeSortedLists(oddList.next, evenList);
    }

    private static ListNode mergeSortedLists(ListNode oddList, ListNode evenList) {
        ListNode dummyNode = new ListNode();
        ListNode cur = dummyNode;
        while (oddList != null || evenList != null) {
            if (oddList != null) {
                cur.next = oddList;
                oddList = oddList.next;
                cur = cur.next;
                cur.next = null;
            }
            if (evenList != null) {
                cur.next = evenList;
                evenList = evenList.next;
                cur = cur.next;
                cur.next = null;
            }
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        ListNode listNode = sortList(new ListNode(1, new ListNode(8, new ListNode(3, new ListNode(6, new ListNode(5,
                new ListNode(4, new ListNode(7, new ListNode(2)))))))));
        System.out.println(listNode);
    }
}