分离单个LinkedList,使所有奇数节点显示在一起,偶数节点显示在一起

2024-03-29 12:19:49 发布

您现在位置:Python中文网/ 问答频道 /正文

给定一个单链表,将所有奇数编号的节点分组在一起,然后是偶数编号的节点。你知道吗

你应该试着在适当的地方做。程序应该在O(1)空间复杂度和O(节点)时间复杂度下运行。你知道吗

例1:

输入:1->;2->;3->;4->;5->;空 输出:1->;3->;5->;2->;4->;空 例2:

输入:2->;1->;3->;5->;6->;4->;7->;空 输出:2->;3->;6->;7->;1->;5->;4->;空 注:

偶数组和奇数组内的相对顺序应保持在输入中的顺序。 第一个节点被认为是奇数,第二个节点被认为是偶数,依此类推。你知道吗

我试着在StackOverflow上查找这个问题,虽然我找到了很多答案,但没有一个答案能回答为什么我的代码会被破坏。另外,我正在使用Python3,所以我无法理解编写的代码。具体来说,我想知道为什么我的代码不起作用。你知道吗

所以,我已经为这个问题编写了代码。但是,当我在计算机上运行此代码时,它不起作用。你知道吗

我的逻辑很简单。首先,我存储第二个节点的值,因为它将是我列表的偶数部分中的第一个节点。你知道吗

然后,取第一个节点的值,并将其指针指向下一个节点的下一个节点。最后,我们将看到一个场景,其中最后一个节点是列表奇数部分中的最后一个节点。你知道吗

因为我已经存储了列表后半部分的第一个节点,所以我现在需要做的就是让最后一个节点的指针指向第一个节点。我不返回一个值,因为只要我调用每个节点上的下一个\节点,我就会得到一个与之前不同的值。你知道吗

def oddEvenNodes(root_node):    
  #Here I store the value of the second node
  if root_node.next_node is None:
    return root_node
  else:
    second_node=root_node.next_node
    node_val=root_node
    prev_node=root_node

 #This is where the actual removing takes place
   while node_val.next_node.next_node is not None:
      prev_node=node_val
      node_val=node_val.next_node
      prev_node.next_node=prev_node.next_node.next_node
  node_val.next=second_node

Tags: the代码gtnode列表节点isval
1条回答
网友
1楼 · 发布于 2024-03-29 12:19:49

算法的思想是正确的,但错误在最后一行:

node_val.next=second_node

首先,没有next属性;它应该是next_node。但是,只有当node_val是奇数节点时,这才是正确的。当它是偶数节点时,您需要为列表中的另一个节点(最后一个奇数节点)执行此赋值。在这种情况下,当前的应该得到None作为next_node。你知道吗

所以,为了知道最终的节点是奇数还是偶数,可以引入一个计数器。更正后的代码如下所示:

def oddEvenNodes(root_node):    
    if root_node.next_node is None:
        return root_node # Note: no need for ELSE after a RETURN
    second_node = root_node.next_node
    node_val = root_node
    prev_node = root_node
    count = 0 # Added this counter
    while node_val.next_node.next_node is not None:
        count += 1 # Keep track of odd/even
        prev_node = node_val
        node_val = node_val.next_node
        prev_node.next_node = node_val.next_node # Note: shorter way
    if count % 2: # Need different treatment when node is even
        node_val.next_node.next_node = second_node
        node_val.next_node = None
    else: # For odd node: do what you already did, but with bug-fix
        node_val.next_node = second_node
    return root_node # Add this to be consistent with other RETURN

相关问题 更多 >