C++链表(四)

⑤.单链表插入节点？

解析：
向单链表中某个位置（第pos个节点）之后插入节点，这里分为插入到链表首部、插入到链表中间，以及链表尾端三种情况：
1 //在单链表pos位置处插入节点，返回链表头指针
2 //pos从0开始计算,0表示插入到head节点后面
3 node *insert_node(node *head, int pos, int data)
4 {
5 node *item = NULL;
6 node *p;
7
8 item = (node *)malloc(sizeof(node));
9 item->data = data;
10 if (pos == 0) //插入链表头后面
11 {
12 head->next = item; //head后面是item
13 return head;
14 }
15 p = search_node(head, pos); //获得位置pos的节点指针
16 if (p != NULL)
17 {
18 item->next = p->next; //item指向原pos节点的后一个节点
19 p->next = item; //把item插入到pos的后面
20 }
21 return head;
22 }

⑥.单向链表删除节点？

解析：
单链表删除节点：
1 //删除单链表的pos位置的节点，返回链表头指针
2 //pos从1开始计算，1表示删除head后的第一个节点
3 node *delete_node(node *head, int pos)
4 {
5 node *item = NULL;
6 node *p = head->next;
7 if (p == NULL) //链表为空
8 {
9 printf("link is empty!\n");
10 return NULL;
11 }
12 p = search_node(head, pos-1); //获得位置pos的节点指针
13 if (p != NULL && p->next != NULL)
14 {
15 item = p->next;
16 p->next = item->next;
17 delete item;
18 }
19 return head;
20 }

⑦.单向链表的逆序？

解析：
这是一个经常被问到的面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过逆置后成为5->4->3->2->1。
最容易想到的方法是遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。
1 node *reverse(node *head)
2 {
3 node *p, *q, *r;
4
5 if (head->next == NULL) //链表为空
6 {
7 return head;
8 }
9
10 p = head->next;
11 q = p->next; //保存原第二个节点
12 p->next = NULL; //原第一个节点为末节点
13
14 while(q != NULL) //遍历，各个节点的next指针反转
15 {
16 r = q->next;
17 q->next = p;
18 p = q;
19 q = r;
20 }
21 head->next = p; //新的第一个节点为原末节点
22 return head;
23 }

⑧.单链表的正向排序？

解析：
下面试结构体定义和代码如下：
1 typedef struct node
2 {
3 int data;
4 node *next;
5 }n