题目链接

LC-143. 重排链表

图解

偶数个节点的情况：

奇数个节点的情况：

时间复杂度 O(n)

Python3 代码

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next or not head.next.next:
            return head

        # 第1遍扫描，找到中点
        fast = head
        slow = head
        while fast and fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        mid = slow

        # 第2遍扫描，将后半段的指针都反向
        a = mid.next
        b = a.next
        mid.next = None
        a.next = None

        while b:
            t = b.next
            b.next = a
            a = b
            b = t

        # 第3遍扫描，将后半段交替插入前半段
        b = head
        while a:
            t = a.next
            a.next = b.next
            b.next = a
            b = b.next.next
            a = t

        return head