Python链表如何通过负索引获取对应节点？

嘿，作为Python链表初学者，想要给_get_node方法加负索引功能其实很简单，咱们一步步来搞定它！

首先得明确负索引的逻辑：和Python列表一样，负索引是从链表末尾开始计数的。比如链表长度为3时，-1对应最后一个节点（正索引2），-2对应中间节点（正索引1），-3对应第一个节点（正索引0），如果负索引的绝对值超过链表长度，就会越界。

修改后的完整_get_node方法 #

def _get_node(self, index):
    # 先获取链表长度，假设你的链表已经正确实现了__len__方法
    list_length = len(self)
    
    # 处理负索引转换
    if index < 0:
        adjusted_index = list_length + index
        # 转换后索引仍然小于0，说明负索引越界
        if adjusted_index < 0:
            raise IndexError("Negative index out of range")
    else:
        adjusted_index = index
        # 检查正索引是否越界
        if adjusted_index >= list_length:
            raise IndexError("Positive index out of range")
    
    # 遍历到目标节点
    current_node = self.head
    for _ in range(adjusted_index):
        current_node = current_node.next
    return current_node

关键步骤解释 #

• 负索引转换：把负索引转换成对应的正索引，核心公式是adjusted_index = 链表长度 + 负索引，这样就能把-1转换成length-1，直接复用正索引的遍历逻辑。
• 越界检查：不管正负索引，转换后都要确保索引在0到list_length-1之间，否则抛出对应的越界错误。
• 节点遍历：和原来的正索引逻辑一致，从head节点开始，遍历adjusted_index次就能拿到目标节点。

举个例子：如果你的链表是[1,2,3]（长度3），调用_get_node(-1)时，adjusted_index = 3 + (-1) = 2，遍历2次后就会指向值为3的节点，和列表的a_list[-1]效果完全一致！

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