Python程序：打印链表倒数第N个节点

更多Python相关文章，请阅读：Python 教程

前言

在日常编程中，操作链表是非常常见的，但是遇到某些特殊需求时，有时候需要查找链表的倒数第N个节点。这时候，如果我们遍历链表两遍，第一遍统计链表的长度，第二遍查找倒数第N个节点，这样的时间复杂度就会达到O(n²)，效率非常低下。实际上，我们可以用一次遍历的方式，找到链表的倒数第N个节点，具体方法如下。

方法

我们可以用两个指针来实现。第一个指针先向前走N步，然后第二个指针开始往前走。当第一个指针走到链表末尾时，第二个指针就恰好走到链表的倒数第N个节点处。

示例代码：

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

def print_nth_from_end(head: ListNode, n: int) -> ListNode:
    if not head:
        return None

    slow, fast = head, head
    for _ in range(n):
        if not fast:
            return None
        fast = fast.next

    while fast.next:
        slow = slow.next
        fast = fast.next

    return slow

# 测试用例
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

print(print_nth_from_end(node1, 2).val)    # 输出 4