Python单链表堆排序中数组拆分返回None数组问题排查

问题场景 #

自行实现list_node（链表节点）和linked_list（单链表）类，尝试将链表节点存入数组后拆分为每组2个元素的子数组以进行堆排序，但运行后数组全为None，期望输出格式为[[A,B],[C,D],[E]]（其中A/B/C/D/E为对应链表节点对象）。

原代码及运行输出 #

import numpy as np
import math as mt

class list_node:
    def __init__(self,obj,next_listnode):
        self.obj = obj
        self.next_listnode  = next_listnode

class linked_list:
    def __init__(self,list_node):
        self.list_node =list_node

    def add_node(self,obj):
        current = self.list_node
        while current.next_listnode is not None:
            current = current.next_listnode
        current.next_listnode = obj;

    def print_linkedlist(self):
        current  = self.list_node
        while current:
            print("",current.obj)
            print("\n")
            current = current.next_listnode

    def delete_node(self,obj):
        current  = self.list_node
        if current.obj is  obj:
            target = current.next_listnode
            self.list_node = current.next_listnode
            del target
        else:
            while current.next_listnode.obj is not obj:
                current = current.next_listnode
            target = current.next_listnode
            current.next_listnode = current.next_listnode.next_listnode
            del target

    def heap_sort(self):
        x = 0
        current = self.list_node
        while current:
            current = current.next_listnode
            x=x+1
        print(x)

        arr = [None]*x
        x = 0
        while current:
            arr[x] = current
            current = current.next_listnode
            x = x+1
        newarr= np.array_split(arr,mt.ceil(len(arr)/2))
        print(newarr)


A = list_node("John",None)
B = list_node("Mike",None)
C = list_node("Han",None)
D = list_node("Daisy",None)
E = list_node("Piggy",None)

liste = linked_list(A)
liste.add_node(B)
liste.add_node(C)
liste.add_node(D)
liste.add_node(E)
liste.heap_sort()

运行输出：

5
[array([None, None], dtype=object), array([None, None], dtype=object), array([None], dtype=object)]

错误原因 #

在heap_sort方法中，第一个while循环用于统计链表长度，遍历结束后current已经指向链表末尾的None。第二个while循环直接以这个None作为起始判断条件，循环根本不会执行，导致arr始终是初始化的全None数组。

修复方案 #

统计完链表长度后，将current重新指向链表头节点self.list_node，再执行填充数组的循环。

修复后的heap_sort方法 #

def heap_sort(self):
    x = 0
    current = self.list_node
    while current:
        current = current.next_listnode
        x += 1
    print(x)

    arr = [None]*x
    x = 0
    # 重置current到链表头
    current = self.list_node
    while current:
        arr[x] = current  # 若需要展示节点的obj属性，可改为current.obj
        current = current.next_listnode
        x += 1
    newarr= np.array_split(arr,mt.ceil(len(arr)/2))
    print(newarr)

运行结果（存储节点对象的情况） #

5
[array([<__main__.list_node object at 0x102345678>, <__main__.list_node object at 0x1023456a0>], dtype=object), array([<__main__.list_node object at 0x1023456c8>, <__main__.list_node object at 0x1023456f0>], dtype=object), array([<__main__.list_node object at 0x102345718>], dtype=object)]

如果需要直观展示节点的内容，将arr[x] = current改为arr[x] = current.obj，输出会显示节点存储的字符串值：

5
[array(['John', 'Mike'], dtype='<U5'), array(['Han', 'Daisy'], dtype='<U5'), array(['Piggy'], dtype='<U5')]

额外优化建议 #

可以合并统计长度和填充数组的步骤，一次遍历完成，减少时间开销：

def heap_sort(self):
    arr = []
    current = self.list_node
    while current:
        arr.append(current)  # 或current.obj
        current = current.next_listnode
    print(len(arr))
    newarr= np.array_split(arr,mt.ceil(len(arr)/2))
    print(newarr)

内容的提问来源于stack exchange，提问作者Volpina