算法通关村第一关--链表青铜挑战笔记

如何构建链表

链表的定义

c:

struct LNode{
	int data; //数据域 
	struct LNode *next; //指针域 
}; 
1
2
3
4

链表的常用操作

增

头插法：

newnode->next = head;//新创的节点的指针域存放head的地址
head = newnode;
1
2

从中间插入：
举例：在 7 前面插入一个数，
先创建一个节点(newnode)，让这个节点的指针域指向 7 所在的节点，接着让 15 所在节点的指针域指向newnode,这样就完成了一次数据的插入。

可不可以颠倒顺序呢，先让 15 节点指针域指向newnode,newnode再指向 7？
不可以，为什么？
在单链表里面一个节点的指针域只存放一个节点的地址，15 节点的指针域存放着 7 节点的地址。如果先让 15 节点先指向newnode 那么就会造成找不到 7 节点的情况。

尾插法
在40 节点后插入一个新节点。这里只需要判断一个节点的指针域是否为null就行。
如果为空，40 节点的指针域存newnode 节点的地址即可。

删

删除头节点
删除头节点只需要将原先head 的next指向head
就比如原先head 是 4 ，4 的next 是 15 ，将15 节点的地址赋给 head,那么此时head 就是15 节点

删除最后一个节点
比如删除 40 这个节点，在删除前我们要注意判断一个节点的下一个节点数据域是不是 40，是的话将这个节点的指针域改为null,这样就无法找到40 节点的地址，就将40 节点删除了。

删除中间节点

就比如删除 7 这个节点，
需要将40 节点的地址存在15 节点的指针域，这样 15 节点的next 就是 40 节点。

cur.next =  cur.next.next 
1