1。链表的结构

2，链表的初始化

3，创建节点

4，尾插

5，头插

6，查找

7，头删

8，移除

9，合并两个有序链表，合并后依然有序

Plist merge(Plist head3,Plist head4) { if (head3 == NULL) return head4; if (head4 == NULL) return head3; Plist p = NULL; Plist cur1 = head3; Plist cur2 = head4; Plist tail = NULL; if (cur1->data < cur2->data) { p = cur1; cur1 = cur1->next; tail = p; } else { p = cur2; cur2 = cur2->next; tail = p; } while (cur1&&cur2) { if (cur1->data< cur2->data) { tail->next=cur1; cur1 = cur1->next; tail = tail->next; } else { tail->next = cur2; cur2 = cur2->next; tail = tail->next; } } if (cur1) { tail->next = cur1; return p; } if (cur2) { tail->next=cur2; return p; } }

10，逆制一个链表

11，查找链表的中间节点

12，删除倒数第k个节点

13，链表的排序

14，把奇数放在偶数前面

Plist jishu_front(Plist head)//把链表奇数放在偶束前面 { if (head == NULL) { printf("the chain is null\n"); return NULL; } Plist tmp = NULL; Plist cur = head; Plist newHead = NULL; Plist oushuhead = NULL; while (cur) { tmp = cur; cur = cur->next; if (tmp->data % 2 == 1) { tmp->next = newHead; newHead = tmp; } if (tmp->data % 2 == 0) { tmp->next = oushuhead; oushuhead = tmp; } } Plist head1 = newHead; while (head1->next != NULL) { head1 = head1->next; } head1->next = oushuhead; return newHead; }

测试代码

完整代码

typedef int DataType; typedef struct Listnode { DataType data; struct Listnode *next; }List,*Plist; void Init(Plist&head) { head = NULL; } Plist _CreatNode(DataType num) { Plist p = (Plist)malloc(sizeof(List)); if (p == NULL) { printf("申请失败。。。\n"); exit(EXIT_FAILURE); } p->data = num; return p; } void PushBack(Plist&head,DataType num) { Plist p = _CreatNode(num); if (head == NULL) { head= p; p->next = NULL; } else { Plist cur = head; while (cur->next) { cur = cur->next; } cur->next = p; p->next = NULL; } } void Pushfront(Plist &head,DataType num) { if (head == NULL) { PushBack(head,num); } else { Plist p=head; Plist s = _CreatNode(num); head = s; s->next = p; } } Plist find(Plist &head,DataType x) { Plist cur = head; if (head->data == x) return head; while (cur->next) { if (cur->next->data == x) return cur; cur = cur->next; } return NULL; } void Popfront(Plist &head) { if (head == NULL) { return; } Plist Head = head; if (head->next == NULL) { head = NULL; } else { head = head->next; } free(Head); } void remove(Plist &head,DataType x) { if (head == NULL) { printf("this chain is NULL\n"); return; } Plist p = find(head, x); if (head == p) { Popfront(head); } if (p == NULL) { printf("not the data\n"); return; } p->next = p->next->next; } Plist merge(Plist head3,Plist head4) { if (head3 == NULL) return head4; if (head4 == NULL) return head3; Plist p = NULL; Plist cur1 = head3; Plist cur2 = head4; Plist tail = NULL; if (cur1->data < cur2->data) { p = cur1; cur1 = cur1->next; tail = p; } else { p = cur2; cur2 = cur2->next; tail = p; } while (cur1&&cur2) { if (cur1->data< cur2->data) { tail->next=cur1; cur1 = cur1->next; tail = tail->next; } else { tail->next = cur2; cur2 = cur2->next; tail = tail->next; } } if (cur1) { tail->next = cur1; return p; } if (cur2) { tail->next=cur2; return p; } } Plist reverse(Plist head) { Plist newHead = NULL; Plist cur = head; Plist tmp = NULL; while (cur) { tmp=cur; cur = cur->next; tmp->next = newHead; newHead = tmp; } return newHead; } Plist find_mid_node(Plist head) { if (head == NULL) { printf("the chain is NULL\n"); return NULL; } if (head->next == NULL||head->next->next==NULL) { return head; } Plist fast = head; Plist slow = head; while (fast->next&&fast->next->next) { fast = fast->next->next; slow = slow->next; } return slow; } void delete_k_node(Plist head,int k) { Plist front = head; Plist back = head; while (front) { k--; if (k<0) { back = back->next; } front = front->next; } if (k < 0) { back->data = back->next->data; Plist del = back->next; back->next = back->next->next; free(del); } } Plist _Sort(Plist head) { if (head == NULL) { printf("the chain is NULL\n"); return NULL; } Plist tail = NULL; Plist cur1 = NULL; for (Plist cur = head; cur->next!= NULL; cur = cur->next) { for (cur1 = head; cur1->next != tail; cur1 = cur1->next) { if (cur1->data > cur1->next->data) { swap(cur1->data, cur1->next->data); } } tail = cur1; } return head; } Plist jishu_front(Plist head)//把链表奇数放在偶束前面 { if (head == NULL) { printf("the chain is null\n"); return NULL; } Plist tmp = NULL; Plist cur = head; Plist newHead = NULL; Plist oushuhead = NULL; while (cur) { tmp = cur; cur = cur->next; if (tmp->data % 2 == 1) { tmp->next = newHead; newHead = tmp; } if (tmp->data % 2 == 0) { tmp->next = oushuhead; oushuhead = tmp; } } Plist head1 = newHead; while (head1->next != NULL) { head1 = head1->next; } head1->next = oushuhead; return newHead; } int main() { Plist head2 ; Plist head1; Init(head2); Init(head1); PushBack(head1, 1); PushBack(head1, 2); PushBack(head1, 3); PushBack(head2,5); PushBack(head2, 4); PushBack(head2, 6); PushBack(head2, 7); Plist l = merge(head1,head2); Plist h=reverse(l); Plist a = find_mid_node(h); Plist g=_Sort(h); Plist m=jishu_front(g); /*delete_k_node(h,2);*/ printf("%d\n",a->data); }