python求链式线性表倒数第k

在Python中，链式线性表（也称为单链表）通常由节点组成，每个节点包含数据和指向下一个节点的引用。如果需要找到链表的倒数第k个元素，可以采用迭代或递归的方法。这里我们提供一种基于迭代的解决方案：

首先，我们需要创建一个Node类来表示链表的节点，然后定义一个函数`get_kth_from_end(linked_list, k)`：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

def get_kth_from_end(head, k):
    if not head or not head.next or k <= 0:
        return None  # 如果链表为空，或者k小于等于0，返回None

    slow_ptr = head  # 慢指针，每次移动1步
    fast_ptr = head  # 快指针，每次移动k步

    for _ in range(k):  # 快指针先移动k步到达链表尾部
        if fast_ptr is None:
            return None
        fast_ptr = fast_ptr.next

    while fast_ptr is not None:  # 当快指针到达尾部，慢指针还在k位置
        fast_ptr = fast_ptr.next
        slow_ptr = slow_ptr.next

    return slow_ptr.data  # 返回慢指针处的数据，即倒数第k个节点

# 示例链表：1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

# 调用函数获取倒数第2个元素
k = 2
result = get_kth_from_end(head, k)
print(f"倒数第{k}个元素是: {result}")