题解 | 重排链表

# 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:#如果是空链表或单节点链表，直接返回
            return 
        slw, fst = head, head
        while fst and fst.next:#快慢指针寻找链表中间位置
            slw, fst = slw.next, fst.next.next
        pre, cur, slw.next = None, slw.next, None
        while cur:#翻转链表第二部分
            tmp = cur.next
            cur.next, pre, cur = pre, cur, tmp
        fst, scd = head, pre
        while scd:#两部分链表进行拼接
            tmp1, tmp2 = fst.next, scd.next
            fst.next = scd
            scd.next = tmp1
            fst, scd = tmp1, tmp2