在链表中插入节点非常容易。如图 4-6 所示,假设我们想在相邻的两个节点
和
之间插入一个新节点
,则只需改变两个节点引用(指针)即可,时间复杂度为 O(1) 。
我试着向程序中添加一个插入链表的代码:
- void insert(ListNode *n0, ListNode *p)
- {
- if(n0 == NULL)
- {
- return;
- }
- if (p == NULL){
- return;
- }
-
- p->next = n0->next;
- n0->next = p;
-
- }
在主程序中新建一个节点,执行打印后再进行打印输出,整个代码如下:
-
-
-
-
- typedef struct ListNode {
- int val;
- struct ListNode *next;
- } ListNode;
-
- ListNode *newListNode(int val) {
- ListNode *node;
- node = (ListNode *) malloc(sizeof(ListNode));
- node->val = val;
- node->next = NULL;
- return node;
- }
-
- void insert(ListNode *n0, ListNode *p)
- {
- if(n0 == NULL)
- {
- return;
- }
- if (p == NULL){
- return;
- }
-
- p->next = n0->next;
- n0->next = p;
-
- }
-
-
- int main(void)
- {
- ListNode* n0 = newListNode(1);
- ListNode* n1 = newListNode(31);
- ListNode* n2 = newListNode(21);
- ListNode* n3 = newListNode(4);
- ListNode* n4 = newListNode(5);
- //构建节点之间的引用
- n0->next = n1;
- n1->next = n2;
- n2->next = n3;
- n3->next = n4;
- //打印出所有值
- ListNode *p;
- p = n0;
- while(p)
- {
- printf("Node val: %d \r\n",p->val);
- p = p->next;
-
- }
- //插入一个新节点
- ListNode* newNode = newListNode(99);
- if(newNode != NULL)
- {
- insert(n0,newNode);
- }
- //打印出所有值
- printf("insert Node\r\n");
- p = n0;
- while(p)
- {
- printf("Node val: %d \r\n",p->val);
- p = p->next;
-
- }
执行后效果如下:
- liujianhuadeiMac:hello_book liujianhua$ gcc node_test.c
- liujianhuadeiMac:hello_book liujianhua$ ./a.out
- Node val: 1
- Node val: 31
- Node val: 21
- Node val: 4
- Node val: 5
- insert Node
- Node val: 1
- Node val: 99
- Node val: 31
- Node val: 21
- Node val: 4
- Node val: 5
- free all
从上面的试验结果可以看到,我们插入节点是成功的。