重排链表

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

问题形容

LeetCode 143. 重排链表

给定一个单链表 L 的头节点head ，单链表 L 示意为：L0 -> L1 -> ... -> Ln-1 -> Ln，将其重新排列后变成 L0 -> Ln -> L1 -> Ln-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)。