数据结构之链表

# 1 字符串

C/C++ 中字符串一般以 '\0' 作为结尾，因此可以很方便地寻找字符串的最后。

但是注意字符串的实际长度要考虑 '\0' 的存在。

字符串的拷贝一般从后向前，可以避免覆盖以及额外的工作量。

# 2 链表

链表是一种动态的数据结构，因为在创建链表时，不需要知道链表的长度。

由于没有闲置的内存，链表的空间效率比数组高。

由于链表的内存不是一次性分配的，因而无法保证链表的内存是连续的。

所以不能像数组一样访问，如果要访问第 i 个节点，就得从第一个开始遍历，时间效率为 O(n)。

但在数组中，我们可以根据下标在 O(1) 时间内找到第 i 个元素。

当作为函数参数传递时，一般用链表的头节点来传递一个链表。

# 2.1 链表节点删除（0616更新）

在 O(1) 时间内完成单向链表的删除，原本删除链表节点需要遍历。

但是如果可以保证要删除的节点一定在链表中，就可以将该节点的下一个节点的值复制过来，并删除下一个节点。

该方法的时间复杂度为 O(1)。但需考虑尾节点以及单节点链表这些特殊情况。

# 2.2 链表遍历（0617更新）

通常的链表遍历都是用一个指针，但有时候它并不能解决问题，比如倒数第 k 个节点（只遍历一次），比如求链表中间节点等。

此时，就可以尝试用两个指针来遍历链表。让其中一个指针遍历的速度快一些（比如一次走两步），或者让它先走若干步。