143. 重排链表

https://leetcode-cn.com/problems/reorder-list/

给定一个单链表 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.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        node_list = []
        cur = head
        while cur:
            node_list.append(cur)
            cur = cur.next

        i, j = 0, len(node_list) - 1
        while i < j:
            node_list[i].next = node_list[j]
            i += 1
            if i == j:
                break
            node_list[j].next = node_list[i]
            j -= 1
        node_list[i].next = None

---

通过观察，可以将重排链表分解为以下三个步骤：

首先重新排列后，链表的中心节点会变为最后一个节点。所以需要先找到链表的中心节点 可以按照中心节点将原始链表划分为左右两个链表。 2.1. 按照中心节点将原始链表划分为左右两个链表，左链表：1->2->3 右链表：4->5。 2.2. 将右链表反转，就正好是重排链表交换的顺序，右链表反转：5->4。 合并两个链表，将右链表插入到左链表，即可重新排列成：1->5->2->4->3.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        middle_node = self.find_middle(head)
        left = head
        right = middle_node.next
        middle_node.next = None
        right = self.reverse(right)
        self.merge(left, right)

    def find_middle(self, head):
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

    def merge(self, left, right):
        while left and right:
            left_temp = left.next
            right_temp = right.next

            left.next = right;
            right.next = left_temp

            left = left_temp
            right = right_temp