获取单链表第 n 个元素

1. 简介

单链表（Singly Linked List）是编程中最常用的数据结构之一，广泛应用于各类高级语言中，例如：

C++ STL 中的 std::forward_list
Scala 和 F# 中的 List

单链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用。

在本教程中，我们将学习如何通过遍历单链表来获取第 n 个节点的值。这在实际开发中非常常见，比如在实现某些自定义容器或解析链式结构时。

2. 获取第 n 个节点的算法

我们要实现一个函数，用于获取链表中第 n 个节点的数据。要实现这个功能，核心思路是：

✅ 从头节点开始，逐个向后移动指针，直到达到索引 n 所在的位置。

以下是伪代码实现：

algorithm GetItem(head, n):
    current <- head
    i <- 0
    while current != null:
        if i == n:
            return current.data
        current <- current.next
        i <- i + 1

⚠️ 注意：如果 n 超出链表长度，应返回错误或空值，避免程序崩溃。

3. GetItem(head, n) 执行流程详解

我们从链表头节点开始：

初始化指针 current = head，计数器 i = 0
进入循环，判断 current 是否为 null（防止空指针异常）
如果 i == n，返回当前节点数据
否则，current = current.next，i++
循环继续，直到找到目标节点或到达链表末尾

示意图如下：

linked list traversal 01

当 current 移动到下一个节点时：

linked list traversal 02

✅ 重点：遍历时必须检查是否越界，否则可能引发 NullPointerException。

4. 获取链表倒数第 n 个节点的算法

我们还可以扩展算法，用于获取链表中倒数第 n 个节点。

比如：

尾节点是倒数第 1 个（索引 -1）
倒数第二个节点是索引 -2
以此类推

伪代码如下：

algorithm GetItemFromEnd(head, n):
    runner <- head
    i <- 0

    while runner != null:
        if i == n:
            break
        runner <- runner.next
        i <- i + 1

    if runner == null:
        print "The list is smaller than n elements"
        return

    trail <- head
    while runner.next != null:
        runner <- runner.next
        trail <- trail.next

    return trail.data

5. GetItemFromEnd(head, n) 执行流程详解

该算法使用双指针技巧：

初始化 runner = head，i = 0
让 runner 向前移动 n 次，这样它和 trail 的距离是 n
如果在移动过程中 runner == null，说明链表长度不足 n，返回错误
否则，初始化 trail = head，同时移动 runner 和 trail，直到 runner.next == null
此时 trail 指向倒数第 n 个节点

示意图如下：

linked list traversal 04

当 runner 到达尾节点时：

linked list traversal 05

✅ 技巧：双指针法在链表问题中非常实用，比如判断是否有环、找中点等。

6. Python 实现

6.1 定义链表结构

Python 内置的 list 是动态数组，无法模拟链表行为。因此我们需要自定义：

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

6.2 实现 get_item 方法

class LinkedList:
    # ... 其他方法

    def get_item(self, n):
        runner = self.head
        count = 0
        while runner:
            if count == n:
                return runner.data
            count += 1
            runner = runner.next
        print("Error: Index out of bounds")
        return None

使用示例：

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)

item = ll.get_item(3)
print("第3个元素是:", item)  # 输出 4

6.3 实现 get_item_from_end 方法

class LinkedList:
    # ... 其他方法

    def get_item_from_end(self, n):
        runner = self.head
        trailer = self.head
        count = 0

        while count < n:
            if runner is None:
                print("Error: Index out of bounds")
                return None
            runner = runner.next
            count += 1

        while runner:
            runner = runner.next
            trailer = trailer.next

        return trailer.data

使用示例：

item = ll.get_item_from_end(3)
print("倒数第3个元素是:", item)  # 输出 3

7. 小结

我们学习了两种链表操作方法：

✅ 获取链表第 n 个节点：

初始化 current = head
移动 n 次，返回当前节点数据

✅ 获取链表倒数第 n 个节点：

使用双指针法，初始化 runner 和 trailer
runner 提前移动 n 次
然后同时移动两个指针，直到 runner 到达尾节点
此时 trailer 指向倒数第 n 个节点

💡 踩坑提醒：

链表操作容易越界，务必检查 null 引用
双指针法在链表问题中非常高效，值得掌握
Python 没有原生链表结构，需手动实现

这些方法在实际开发中非常有用，例如实现 LRU 缓存、解析复杂数据结构等场景。

Persistence

REST

Security