# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
# 学习中……
class Solution:
    def reversenode(self, root):
        pre = None
        while root:
            temp = root.next 
            root.next = pre 
            pre = root 
            root = temp 
        return pre 
    
    def sortLinkedList(self , head: ListNode) -> ListNode:
        # 奇偶取出，偶反转
        if not head or not head.next:
            return head 
        odd = head
        even = head.next
        even_head = even 
        while even and even.next:
            odd.next = even.next 
            odd = odd.next 
            even.next = odd.next 
            even = even.next
        odd.next = None # 截断 
        # 如果even为None 说明是奇数列odd是最后一位，如果even.next为空说明是偶数
        # 此时head已经发生变化 head是奇数列头节点 head.next 是奇数位了
        newhead = self.reversenode(even_head)  # 反转偶数链表 
        dummy = ListNode(0)
        cur = dummy 
        while head and newhead:
            if head.val <= newhead.val:
                cur.next = head 
                head = head.next 
            else:
                cur.next = newhead 
                newhead = newhead.next 
            cur = cur.next
        cur.next = head if head else newhead # 最后如果奇数还有数连接到末尾否则是偶数
        return dummy.next