143. 重排链表

难度中等428收藏分享切换为英文接收动态反馈

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

解题思路

方法一：线性表

因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。

因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。

复杂度分析

时间复杂度：O(N)，其中 N 是链表中的节点数。

空间复杂度：O(N)，其中 N 是链表中的节点数。主要为线性表的开销。

class Solution: def reorderList(self, head: ListNode) -> None: if not head: return vec = list() node = head while node: vec.append(node) node = node.next i, j = 0, len(vec) - 1 while i < j: vec[i].next = vec[j] i += 1 if i == j: break vec[j].next = vec[i] j -= 1 vec[i].next = None

方法二：寻找链表中点 + 链表逆序 + 合并链表

注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。

这样我们的任务即可划分为三步：

找到原链表的中点（参考「876. 链表的中间结点」）。

我们可以使用快慢指针来 O(N)地找到链表的中间节点。 将原链表的右半端反转（参考「206. 反转链表」）。

我们可以使用迭代法实现链表的反转。 将原链表的两端合并。

因为两链表长度相差不超过 1，因此直接合并即可

复杂度分析

时间复杂度：O(N），其中 N 是链表中的节点数。

空间复杂度：O(1)。

class Solution: def reorderList(self, head: ListNode) -> None: if not head: return mid = self.middleNode(head) l1 = head l2 = mid.next mid.next = None l2 = self.reverseList(l2) self.mergeList(l1, l2) def middleNode(self, head: ListNode) -> ListNode: slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow def reverseList(self, head: ListNode) -> ListNode: prev = None curr = head while curr: nextTemp = curr.next curr.next = prev prev = curr curr = nextTemp return prev def mergeList(self, l1: ListNode, l2: ListNode): while l1 and l2: l1_tmp = l1.next l2_tmp = l2.next l1.next = l2 l1 = l1_tmp l2.next = l1 l2 = l2_tmp

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。