python实现获取单向链表倒数第k个结点的值示例

下面就是详细讲解“Python实现获取单向链表倒数第k个结点的值”的攻略。

问题描述

假设有一条单向链表，现在需要找到它的倒数第k个节点的值，应该如何实现呢？

解决思路

方法一：先遍历整个链表，获取链表长度n，然后在从头遍历到n-k个节点，即可获取倒数第k个节点。

方法二：使用快慢指针法，先让快指针走k-1个节点，然后同时走快慢指针，当快指针走到链表尾部时，慢指针指向的就是倒数第k个节点。

Python代码示例

方法一：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def get_kth_from_end(self, head: ListNode, k: int) -> ListNode:
        n = 0
        p = head
        while p:
            n += 1
            p = p.next
        p = head
        for i in range(n-k):
            p = p.next
        return p.val

方法二：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def get_kth_from_end(self, head: ListNode, k: int) -> ListNode:
        fast = slow = head
        for _ in range(k):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow.val

以上是基于Python实现获取单向链表倒数第k个节点的值的示例，供大家参考。