关于leetcode:完虐算法重排链表

重排链表

更多算法题解，请关注公众号【程序员学长】

问题形容

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)。