链表

由于数组在插入和删除操作，都需要后面的结点。内存需要预先分配，扩容不易。

所以有了链表。链表包含一个指向下一个节点的指针和一个自己data域

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成，这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next，Next指向下一个节点，这样当添加或者删除时，只需要改变相关节点的Next的指向，效率很高。

struct Node {
  void * data;
  Node *next;
} Node

头指针：指向链表链表第一个元素的指针

头结点：就是一个含有空的数据域的结点。作为标识。

链表的结构

单链表的操作

• 查找

查找元素的时间复杂度依然是O（n）。需要从头节点遍历。

• 插入

插入一个新的元素到指定的位置，只需要改变前面元素的next指针指向该元素。不需要移动后面的元素。时间复杂度为0（n）

• 删除

删除一个元素的，只需要记住这个元素的前一个元素和后面一个元素。删掉这个元素后，采用覆盖的方法，实现删除。时间复杂度为O（1）

双链表

双链表是包含两个两个指针域和一个data域的链表结构。这样我们可以从两个方向遍历。

struct doubleLink {
  void *data;
  struct doubleLink next;
  struct doubleLink prev;
}

链表相关的面试题

链表是一种基础的数据结构，也是面试中常考的，

• 判断单链表是否有环

可以使用快慢指针来。如果有环，则两个指针会相遇。

• 已知两个单链表相交，求他们的第一个交点

思路：由于两个单链表相交，那么他们的尾节点一定是相同的。遍历两个链表，求出各个长度。然后求出两个链表的差N，然后让长的链表，先走N,慢的链表再同步走。当两个节点相同时。就是一个第一个交点

• 快速找到未知长度单链表的中间节点

思路1：最简单的方法，遍历一次单链表，然后求出长度。然后除以2。找到位置，然后再遍历一次。时间复杂度是O（(3N/2)）

思路2：快慢指针，快的指针比慢指针多走一倍，然后快的指针走到尾，慢指针恰好在中间。

• 约瑟夫环

在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

思路：可以使用循环链表的方法。