1->4->3->2->5 给定一个链表奇数部分递增，偶数部分递减，要求在O(n)时间复杂度内将链表变成递增，5分钟左右

迭代拆分链表

反转偶数位链表，合并两个有序链表。

class Solution {
    public ListNode sortOddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode odd = head; // 奇数位链表的起始节点
        ListNode even = head.next; // 偶数位链表的起始节点
        ListNode evenHead = even; // 保存偶数位链表的头节点，用于后续反转，相当于虚拟节点
        
        // 迭代拆分链表，注意结束条件。even在前面，所以以它为标准。重点。
        while (even != null && even.next != null) {
            odd.next = even.next; // 连接奇数位链表的下一个节点
            odd = odd.next; // 移动到下一个奇数位节点
            
            even.next = odd.next; // 连接偶数位链表的下一个节点
            even = even.next; // 移动到下一个偶数位节点
        }
        odd.next = null;  // 断开奇数链表的最后一个节点，确保链表长度为偶数时不会形成环。重点。

        // 反转偶数位链表
        ListNode reversedEven = reverseList(evenHead);

        // 合并两个有序链表
        return mergeTwoLists(head, reversedEven);
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null; // 前一个节点
        ListNode curr = head; // 当前节点
        
        while (curr != null) {
            ListNode nextTemp = curr.next; // 临时保存下一个节点
            
            curr.next = prev; // 反转当前节点的指向
            
            prev = curr; // 移动前一个节点指针
            curr = nextTemp; // 移动当前节点指针
        }
        return prev; // 返回反转后的链表头节点
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 虚拟头节点，简化操作
        ListNode current = dummy; // 当前节点指针
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) { // 比较两个链表的当前节点值
                current.next = l1; // 将较小值节点连接到当前节点
                l1 = l1.next; // 移动l1指针
            } else {
                current.next = l2; // 将较小值节点连接到当前节点
                l2 = l2.next; // 移动l2指针
            }
            current = current.next; // 移动当前节点指针
        }
        current.next = (l1 != null) ? l1 : l2; // 连接剩余的节点
        return dummy.next; // 返回合并后的链表头节点
    }
}