题解 | 重排链表

# 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 head == None or head.next == None or head.next.next == None:
            return head

        # 1 -> 2 -> 3
        # 1 -> 2 -> 3 -> 4
        # 找到链表中间位置，将链表分解为2个
        # p1，p2快慢指针，p1最终为前半段链表最后一个元素，p2遍历到原链表最后1个元素退出
        p1,p2 = head,head
        while p2.next !=None and p2.next.next !=None:
            p1 = p1.next
            p2 = p2.next.next

        #p1先赋值给half_raw，half_raw为后半段链表开头。
        #p1再将下个元素赋为None，前半段链表结束。
        half_raw = p1.next
        p1.next = None 

        # 翻转后半段链表
        half_new = None
        p = half_raw       
        while p !=None:
            temp = p.next
            p.next = half_new
            half_new = p
            p = temp

        # 合并前、后两个链表
        p1 = head
        p2 = half_new
        while p2!=None:
            temp1 = p1.next
            temp2 = p2.next
            p1.next = p2
            p2.next = temp1
            p2 = temp2
            p1 = temp1

        return head