链表初步

链表创建

顺序建立链表

//input: the number of nodes //return: address of the head node struct node * create(int n) { struct node * p, * q, *head; int i; head = (struct node *)malloc(sizeof(struct node)); head->next = NULL; q = head; for(i = 0;i < n;i++) { p = (struct node *)malloc(sizeof(struct node)); scanf("%d", &p->data); p->next = NULL; q->next = p; q = p; } return head; }

链表输出

//input: the address of the head node //return: none int output(struct node * head) { struct node * p, * q; p = head->next; while(p != NULL) { if(p->next != NULL) { printf("%d ", p->data); } else { printf("%d\n", p->data); } p = p->next; } return 0; }

链表逆置

其一

//input: the address of the head node //return: none int reverse(struct node * head) { struct node * p, * q; p = head->next; head->next = NULL; q = p->next; while(p != NULL) { p->next = head->next; head->next = p; p = q; if(q != NULL) { q = q->next; } } return 0; }

其二

（待补充）

链表归并

//input: the address of two head nodes(head1, head2) //return: the address of head1 struct node * merge(struct node * head1,struct node * head2) { struct node *p1, *p2, *q; p1 = head1->next; p2 = head2->next; q = head1; free(head2); while(p1 && p2) { if(p1->data < p2->data) { q->next = p1; q = p1; p1 = p1->next; } else { q->next = p2; q = p2; p2 = p2->next; } } if(p1) { q->next = p1; } else { q->next = p2; } return (head1); }

链表拆分

（待补充）