[python 刷题] 143 Reorder List
题目:
You are given the head of a singly linked-list. The list can be represented as:
Reorder the list to be on the following form:
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
这道题虽然说不允许修改链表结点上的值,但是改了也能过……那样的解法就是将所有的值保存在一个数组里,然后遍历整个数组,通过判断数组当前所在的结点去修改值。
当然,因为这道题已经明确说了,不允许修改链表结点上的值, 所以这种是能过但是面试情况下是不行的情况 🙅
正确的做法是找到链表的一半,翻转后半段,再一个个交替串联,所以这种情况下来说,[JavaScript 刷题] 链表 – 反转链表, leetcode 206 可以算是这道题的前置题。
这道题唯一需要注意一点的地方在于寻找的中点。
当链表长度为偶数时:
当链表长度为奇数时:
这个时候对链表进行反转并不会产生理想的效果,反而会让中点有两个头,产生这样的效果:
和
这样也就意味着会产生环形链表,所以正确的做法是找到中点前的结点 prev
,在完成翻转后,将 prev
指向空,这样就有了两个不相关的链表,也就不会出现环形链表的情况
最终解法如下:
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
l_fast, l_slow = head.next, head
while l_fast and l_fast.next:
l_slow = l_slow.next
l_fast = l_fast.next
l_fast = l_fast.next
def reverse(node):
if not node or not node.next:
return node
new_head = reverse(node.next)
node.next.next = node
node.next = None
return new_head
l_reversed = reverse(l_slow.next)
l_slow.next = None
while l_reversed:
temp1, temp2 = head.next, l_reversed.next
head.next = l_reversed
l_reversed.next = temp1
head, l_reversed = temp1, temp2
文章出处登录后可见!
已经登录?立即刷新