从一篇单链表题目的文章中学到的总结

单链表简单的计算题

给一个单链表, 拿到它倒数第k个节点.

1. 方法一: 遍历法/硬解法 不可见

[^_^]: 遍历两遍, 第一遍获得链表的长度N, 第二遍则知道链表的倒数k节点是正数第几个节点. 时间复杂度为O(n*2).

2. 方法二: 递归法 不可见

[^_^]: 此例子中有一个特点与递归的情况吻合就是倒数(从后往前), 正好可以利用递归的此特点, 当递归到最后, 返回的时候, 从最后开始计数k个节点, 返回此节点. 时间复杂度为O(n*2).

3. 方法三: 双指针法 此题本意是考量此种解法:不可见

[^_^]: 设两个指针, 一个指针先正向遍历k个节点, 此时两个指针相差k, 然后两个指针开始同时正向遍历, 当先行的那个指针遍历完链表时, 另一个指针所指的节点正是倒数第k个节点, 此种方式时间复杂度为O(n)

链表成环问题

使用链表实现大数加法

有序链表合并

删除链表中的节点

从尾到头打印链表

反转链表