leetcode/src/summarize/linked-list.md at master · codinglin/leetcode

链表的基本操作

要想写出链表的题目，熟悉链表的各种基本操作和复杂度是必须的。

插入只需要考虑要插入位置前驱节点和后继节点（双向链表的情况下需要更新后继节点）即可，其他节点不受影响，因此在给定指针的情况下插入的操作时间复杂度为O(1)。这里给定指针中的指针指的是插入位置的前驱节点。

伪代码：

temp = 待插入位置的前驱节点.next
待插入位置的前驱节点.next = 待插入指针
待插入指针.next = temp

如果没有给定指针，我们需要先遍历找到节点，因此最坏情况下时间复杂度为 O(N)。

提示 1: 考虑头尾指针的情况。

提示 2: 新手推荐先画图，再写代码。等熟练之后，自然就不需要画图了。

只需要将需要删除的节点的前驱指针的 next 指针修正为其下下个节点即可，注意考虑边界条件。

伪代码：

待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next

提示 1: 考虑头尾指针的情况。

提示 2: 新手推荐先画图，再写代码。等熟练之后，自然就不需要画图了。

遍历比较简单，直接上伪代码。

迭代伪代码：

当前指针 =  头指针
while 当前节点不为空 {
   print(当前节点)
   当前指针 = 当前指针.next
}

一个前序遍历的递归的伪代码：

dfs(cur) {
    if 当前节点为空 return
    print(cur.val)
    return dfs(cur.next)
}

注意：快慢指针和链表反转几乎是所有链表类问题的基础，尤其是反转链表，代码很短，建议直接背熟。