题解 | #排序奇升偶降链表#

class Solution:
    def sortLinkedList(self , head: ListNode) -> ListNode:
        # write code here
        if not head.next:    return head
        
        p1, p2 = self.partition(head)
        p2 = self.reverse(p2)
        return self.merge(p1, p2)
    
    def partition(self, head):
        p2Head = head.next
        p1, p2 = head, p2Head
        while p2 and p2.next:
            p1.next = p2.next
            p2.next = p2.next.next
            p1 = p1.next
            p2 = p2.next
        p1.next = None    # 注意这个地方
        return [head, p2Head]
    
    def reverse(self, head):
        pre, cur = None, head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre
    def merge(self, p1, p2):
        dummy = q = ListNode(-1)
        while p1 and p2:
            if p1.val < p2.val:
                q.next = p1
                p1 = p1.next
                q = q.next
            else:
                q.next = p2
                p2 = p2.next
                q = q.next
        if p1:
            q.next = p1
        else:
            q.next = p2
        return dummy.next
# 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