共计 953 个字符,预计需要花费 3 分钟才能阅读完成。
重排链表
更多算法题解,请关注公众号【程序员学长】
问题形容
LeetCode 143. 重排链表
给定一个单链表 L 的头节点 head,单链表 L 示意为:L0 -> L1 -> … -> Ln-1 -> Ln,将其重新排列后变成 L0 -> Ln -> L1 -> Ln-1 -> …。不能只是单纯的扭转节点的值,而须要理论的进行节点的替换。
示例:
输出:head = [1,2,3,4]
输入:[1,4,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)。
正文完