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

Question

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

你应该尽量做到原地踏步。该程序应以 O(1) 空间复杂度和 O(节点) 时间复杂度运行。

示例 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

Answer 1

算法思路是对的，但是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