题解 | #重排链表#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# 
# @param head ListNode类 
# @return void
#
class Solution:
    def reorderList(self , head ):
        # write code here
        
        if not head or not head.next or not head.next.next: 
            return head
            
        #快慢指针找中间位置
        
        slowptr = head
        fastptr = head
        while fastptr.next and fastptr.next.next:
            slowptr = slowptr.next
            fastptr = fastptr.next.next
        head1 = head
        head2 = slowptr.next
        temp1 = None
        
        #反转后半段链表
        
        while head2:
            temp2 = head2.next
            head2.next = temp1
            temp1 = head2
            head2 = temp2
            
        #顺序合并
        
        head2 = temp1
        while head2:
            temp1 = head1.next
            temp2 = head2.next
            head1.next = head2
            head2.next = temp1
            head1 = temp1
            head2 = temp2
            if head2 == None:
                head1.next = None
        return head