我正在编写代码来解决LeetCode的重新订购列表代码挑战:
你会得到一个单链表的头。列表可以表示为:
L0→L1→ … →Ln-1→Ln
将列表重新排序为以下表格:
L0→Ln→L1→Ln-1→L2→Ln-2→ …
您不能修改列表节点中的值。只能更改节点本身。
示例1:
Input: head = [1,2,3,4] Output: [1,4,2,3]
示例2:
Input: head = [1,2,3,4] Output: [1,4,2,3]
这是我的代码:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
def reverseLL(curr):
curr = head
counter = 0
#finding the mid=point of the LL
while curr:
curr=curr.next
counter+=1
if counter%2==0:
counter= counter//2
else:
counter = (counter//2) +1
#this is to make curr2 point at the middle node or the node after the middle
curr2 = head
while counter >=0:
curr2=curr2.next
counter -=1
return curr2
#reversing the second half of the LL (curr2 points to middle node or node after middle if counter is odd)
prev = None
node = reverseLL(head)
while node:
curr_reverse = node.next
node.next = prev
prev = node
node = curr_reverse
#prev is at this point the head of the reversed second half of the linked list
#now we do the reordering
curr = head
prev_nex = None
while prev_nex:
nex= curr.next
curr.next = prev
prev_nex = prev.next
prev.next=nex
prev=prev.nex
curr=nex
return head
当我用笔和纸写出来并通过它运行任何输入时,它是有效的,但由于某种原因,它没有通过测试,特别是对于input=[1,2,3,4]
,它会产生output=[1,2,3,4]
有人能发现任何不一致之处吗?我添加了一些注释来描述我在代码的每个阶段要做的事情。谢谢
存在以下问题:
-
最终的
while prev_nex:
循环永远不会迭代,因为prev_nex
在开始循环之前被初始化为None
。while curr and prev:
可以修复这种情况 -
最后一条语句有一个拼写错误:
prev=prev.nex
实际上应该是prev=prev_nex
-
reverseLL
中的while
循环迭代次数过多。它应该提前停止两个节点。当前,当列表为[1,2,4]时,它会停止在最后一个节点,而它应该真正停止在值为2的节点(或者在节点3处进行一些其他更改(。我在这里建议使用while counter > 1:
,因为这样就不需要对代码进行其他更改。
有了这三个修复程序,您的代码就可以工作了。