更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

重排链表

问题描述

LeetCode 143. 重排链表

给定一个单链表 L 的头节点head ，单链表 L 表示为：L₀ -> L₁ -> ... -> L_n-1 -> L_n，将其重新排列后变成 L₀ -> L_n -> L₁ -> L_n-1 -> ...。不能只是单纯的改变节点的值，而需要实际的进行节点的交换。

示例：

输入： head = [1，2，3，4]

输出： [1，4，2，3]

###分析问题

首先，我们来观察一下链表重置前和重置后的变化。如下图所示：

我们可以知道，重置后的链表是将原链表的左半端和反转后的右半段进行节点交叉合并而成的，所有我们可以分三步来求解。

1. 找到原链表的中点，将链表分割成左右两部分。
2. 对后半部分进行反转。
3. 建原链表的左半部分和反转后的右半部分进行合并。

class Solution:
    def reorderList(self, head):
        #如果链表为空，直接返回
        if not head:
            return
        #寻找链表的中点，将链表分割成左右两部分
        mid = self.middleNode(head)
        left = head
        right = mid.next
        mid.next = None
        #对右半部分的链表进行反转
        right = self.reverseList(right)
        #左右链表进行合并
        self.mergeList(left, right)

    def middleNode(self, head):
        #使用快慢指针法求中点
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    #对链表进行反转
    def reverseList(self, head):
        prev = None
        curr = head
        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
        return prev

    #对两个链表进行合并操作
    def mergeList(self, l1, l2):
        #l1和l2的节点数量相差不会超过一个
        #所以直接合并就好
        while l1 and l2:
            tmp1 = l1.next
            tmp2 = l2.next

            l1.next = l2
            l1 = tmp1

            l2.next = l1
            l2 = tmp2

该算法的时间复杂度是O(N)，空间复杂度是O(1)。