forked from xianyunyh/PHP-Interview
-
Notifications
You must be signed in to change notification settings - Fork 0
/
链表.md
74 lines (42 loc) · 3.02 KB
/
链表.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
## 链表
由于数组在插入和删除操作，都需要后面的结点。内存需要预先分配，扩容不易。
所以有了链表。链表包含一个指向下一个节点的指针和一个自己data域
> 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成，这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next，Next指向下一个节点，这样当添加或者删除时，只需要改变相关节点的Next的指向，效率很高。
```c_cpp
struct Node {
void * data;
Node *next;
} Node
```
头指针：指向链表链表第一个元素的指针
头结点：就是一个含有空的数据域的结点。作为标识。
链表的结构
单链表的操作
- 查找
查找元素的时间复杂度依然是O（n）。需要从头节点遍历。
- 插入
插入一个新的元素到指定的位置，只需要改变前面元素的next指针指向该元素。不需要移动后面的元素。时间复杂度为0（n）
- 删除
删除一个元素的，只需要记住这个元素的前一个元素和后面一个元素。删掉这个元素后，采用覆盖的方法，实现删除。时间复杂度为O（1）
### 双链表
双链表是包含两个两个指针域和一个data域的链表结构。这样我们可以从两个方向遍历。
```c_cpp
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个位置，于是逃过了这场死亡游戏。
思路：可以使用循环链表的方法。