- 创建节点
```
function CreateNode (key) {
this.key = key;
this.next = null;
}
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
| let node1 = new CreateNode(1);
let node2 = new CreateNode(2);
let node3 = new CreateNode(3);
let node4 = new CreateNode(4); ``` > 2. 尾插, > 我们只需要知道头节点, 就可以找到最后一个节点, > 就可以找到任何一个节点 > ```
function insert (node,lastnode) {
while (node.next){
node = node.next;
}
node.next = lastnode;
}
insert(node1,new CreateNode(2));
insert(node1,new CreateNode(3));
insert(node1,new CreateNode(4));
insert(node1,new CreateNode(5)); ``` > 3. 有头节点 ```
let head = {type : "head",next : null};
function insert (head,lastnode) {
while (head.next){
head = head.next;
}
head.next = lastnode;
}
insert(head,new CreateNode(2));
insert(head,new CreateNode(3));
insert(head,new CreateNode(4)); ``` > 4. 任意位置插入 ```
let head = {type : "head",next : null};
function insert (head,node,num = Infinity) {
if (nun < 1) {
return
}
while (head.next && --num > 0){
head = head.next;
}
// 先临时保存
let nextnode = head.next;
// 插入新节点, 此时与原来的next 断开了
head.next = node;
// 重新接上.
node.next = nextnode;
} ``` > 5. 删除 ``` 根据节点删除
function deleteNode (head,node) {
while (head.next){
if (head.next == node) {
head.next = head.next.next;
return
}
head = head.next;
}
}
|
根据节点值删除
function deleteNode (head,key) {
while (head.next){
if (head.next.key === key) {
head.next = head.next.next;
return 此处不return 就是把链表中所有符合条件都干掉
此处return 就表示只干掉第一个满足条件的节点
}
head = head.next;
}
}
根据位置删除? 但实际上位置是相对来讲动态的.
function deleteNode (head,num) {
if (num < 1) {
return
}
while (head.next && num– > 0){
if (num === 0) {
head.next = head.next.next;
return
}
head = head.next;
}
}
1
2
3
4
5
|
> 6. 判断有没有环
> * 取一个步长为一, 取一个步长为二 的 指针
> * 如果出现两个指针相同, 且不为空, 则表明形成环了.
> * 好聪明, 这就像是运动场上的跑步, 当然 步长 1,2 保证一圈内肯定能遇上,
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function findRing (head) {
let point1 = head.next;
let point2 = point1 && point1.next;// head.next.next 有可能报错
while (point1 && point2){ // point1 point1 都存在且不为空
if (point1 === point2) {
return true
}
point1 = point1.next;
point2 = point2.next;
point2 = point2 && point2.next;
}
return false;
} ```
|
