问题描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

• 通过快慢指针，找到中间节点
• 将 list 从中间一分为二
• 将右面的子 list 反转
• 将右面的子列表插入到左面的列表的“缝隙”中

Python 实现

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def print_list(self, p):
        if p is None:
            return
        temp = p
        while temp is not None:
            print(temp.val)
            temp = temp.next

    def revserve(self, node):
        if node is None or node.next is None:
            return node

        p1 = node
        p2 = node.next
        p1.next = None
        while p2 is not None:
            p3 = p2.next
            p2.next = p1
            p1 = p2
            p2 = p3

        return p1

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

        # find the middle node using fast and slow pointer
        slow = fast = head
        while fast is not None and \
                fast.next is not None and \
                fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next

        p1 = head
        # split the list into two lists
        p2 = slow.next
        slow.next = None
        # reverse the second list using three pointer method
        p2 = self.revserve(p2)

        # insert into the grap
        while p2 is not None:
            p1_next = p1.next
            p1.next = p2
            p2_next = p2.next
            p2.next = p1_next

            p1 = p1_next
            p2 = p2_next