LeetCode 143. 重排链表 reorder list Python3解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 只有大于等于三个时才有效
        if head and head.next and head.next.next:
            # 找中点
            p_slow, p_fast = head, head
            while p_fast and p_fast.next:
                p_slow = p_slow.next
                p_fast = p_fast.next.next
            # 后半部分逆序
            p_bh_pre = p_slow.next
            p_slow.next = None
            p_bh_cur = p_bh_pre.next
            node = ListNode(0)
            node.next = p_bh_pre
            while p_bh_cur:
                p_bh_pre.next = p_bh_cur.next
                p_bh_cur.next = node.next
                node.next = p_bh_cur
                p_bh_cur = p_bh_pre.next
            # 插入
            p_qian, p_hou = head, node.next
            while p_qian and p_hou:
            	# 先保留先半部分的下一个节点
                node.next = p_qian.next
                # 插入后半部分的第一个节点
                p_qian.next = p_hou
                # 后半部分后移
                p_hou = p_hou.next
                # 插入后改变next
                p_qian.next.next = node.next
                p_qian = node.next