python实现leetcode之143. 重排链表

解题思路

三步走：
第一步，找到中点，使用快慢指针
第二步，后半部分逆序
第三步，合并前后两个半部分，直到到达中间位置

143. 重排链表

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head: return head
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        bp = slow  # break point跳出的点
        # 后半部分逆序
        p = slow.next
        slow.next = None
        while p:
            tmp = p.next
            p.next = slow
            slow = p
            p = tmp
        # 然后合并
        merge(head, slow, bp)



def merge(x, y, gap):
    if x == gap:
        x.next = None
        return
    if not y: return
    xn = x.next
    yn = y.next
    x.next = y
    y.next = xn
    merge(xn, yn, gap)