时间戳

首页 > 解决方案 > 分离一个单链表，使所有奇数节点一起出现，偶数节点一起出现

python - 分离一个单链表，使所有奇数节点一起出现，偶数节点一起出现

问题描述

给定一个单链表，将所有奇数节点组合在一起，然后是偶数节点。

你应该试着在原地做。程序应该以 O(1) 空间复杂度和 O(nodes) 时间复杂度运行。

示例 1：

输入：1->2->3->4->5->NULL 输出：1->3->5->2->4->NULL 示例 2：

输入：2->1->3->5->6->4->7->NULL 输出：2->3->6->7->1->5->4->NULL 注意：

偶数组和奇数组内的相对顺序应保持与输入中的相同。第一个节点被认为是奇数，第二个节点被认为是偶数，依此类推。

我尝试在 StackOverflow 上查找这个问题，虽然我找到了很多答案，但没有一个回答我的代码为什么会出错。另外，我使用的是 Python3，所以我无法理解编写的代码。具体来说，我想知道为什么我的代码不起作用。

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

我的逻辑很简单。首先，我存储第二个节点的值，因为这将是我列表的偶数一半中的第一个节点。

此后，取第一个节点的值，并获取其指向下一个节点的下一个节点的指针。最后，我们留下了最后一个节点是我列表奇数一半中的最后一个节点的场景。

因为我已经存储了列表后半部分的第一个节点，所以我现在需要做的就是让最后一个节点的指针指向第一个节点。我不返回值，因为只要我在每个节点上调用 next_node，我就应该得到与以前不同的值。

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

标签： pythonpython-3.xalgorithmdata-structureslinked-list

解决方案

算法的思路是对的，但是bug在最后一行：

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

推荐阅读