链表的常见操作

链表

struct List
{int data;struct List* next;
}

创建链表

单链表

实现

struct List* listCreate()
{int data;struct List* head = NULL;struct List* pre = NULL;struct List* current = NULL;while(scanf("%d",&data) && data != -1){current = (struct List*)malloc(sizeof(struct List));if(head == NULL)head = current;elsepre->next = current;current->next = NULL;current->data = data;pre = current;}return head;
}

错例

struct List* listCreate()
{int data;;struct List* current = NULL;struct List* head = current;while (scanf("%d", &data) && data != -1){current = (struct List*)malloc(sizeof(struct List));if (head == NULL)head = current;current->data = data;current = current->next;}return head;
}

在使用malloc函数开辟的空间中，不要进行指针的移动，因为一旦移动之后可能出现申请的空间和释放空间大小的不匹配

循环链表

单独创建

struct List* circle_listCreate()
{int data;struct List* head = NULL;struct List* pre = NULL;struct List* current = NULL;while(scanf("%d",&data) && data != -1){current = (struct List*)malloc(sizeof(struct List));if(head == NULL)head = current;elsepre->next = current;current->next = head;current->data = data;pre = current;}return head;
}

逐节点创建

void Append(struct List** L,int data)
{struct List* head = *L;struct List* newNode = NULL;if((*L) == NULL){(*L) = (struct List*)malloc(sizeof(struct List));(*L)->data = data;head = (*L);(*L)->next = head;}else{while ((*L)->next != head){(*L) = (*L)->next;}newNode = (struct List*)malloc(sizeof(struct List));newNode->data = data;(*L)->next = newNode;newNode->next = head;*L = head;}
}

约瑟夫环问题

void Append(struct List** L,int data)
{struct List* head = *L;struct List* newNode = NULL;if((*L) == NULL){(*L) = (struct List*)malloc(sizeof(struct List));(*L)->data = data;head = (*L);(*L)->next = head;}else{while ((*L)->next != head){(*L) = (*L)->next;}newNode = (struct List*)malloc(sizeof(struct List));newNode->data = data;(*L)->next = newNode;newNode->next = head;*L = head;}
}
void Display(struct List* L,int num)
{struct List* head = L;struct List* pre = NULL;struct List* kill = NULL;int nodeNum = 0;while (L->next != head){nodeNum++;L = L->next;}pre = L;L = L->next;nodeNum++;while (nodeNUm){if (nodeNum == 1){printf("%d",L->data);free(L);return;}for (int i=1; i < m; i++){pre = L;L = L->next;}printf("%d ", L->data);kill = L;L = L->next;free(kill);nodeNum--;}
}

删除节点

实现方式一：

struct list* listDelete(struct list* L,int data)
{struct list* pre = L;struct list* head = L;struct list* kill;while(head != NULL && head->data == m){kill = head;head = head->next;free(kill);}if(head == NULL)return head;pre = head;kill = head->next;while(kill!=NULL){if(kill->data == m){pre->next = kill->next;free(kill);kill = pre->next;}else{pre = kill;kill = kill->next;}}return head;
}

实现方式二：

struct list* listDelete(struct list** L,int data)
{struct list* head = (*L), * pre = (*L);struct list* newL = *L;struct list* kill = NULL;while (*L !- NULL){if((*L)->data == data){if((*L) == newL)newL == newL->next;elsepre->next = (*L)->next;kill = (*L);(*L) = (*L)->next;free(kill);}else{pre = (*L);(*L) = (*L)->next;}}*L = newL;return head;
}

删除节点并建立新链表

struct list* list_Delete_Create(struct list** L) //数据为奇数存为新链表
{struct list* newhead = NULL, * newcurrent = NULL, * newpre = NULL;struct list* newL = *L;struct list* kill = NULL;struct list* pre = *L;while (*L){if((*L)->data%2 == 1){newcurrent = (struct list*)malloc(sizeof(struct list));if(newhead == NULL)newhead = newcurrent;elsenewpre->next = newcurrent;newcurrent->data = (*L)->data;newcurrent->next = NULL;newpre = newcurrent;if((*L) == newL)newL = newL->next;elsepre-next = (*L)->next;kill = (*L);(*L)=(*L)->next;free(kill);}else{pre = (*L);(*L) = (*L)->next;}}*L = newL;return newhead;
}

逆置链表

实现：

struct list* reverse(struct list* L)
{struct list* newhead = NULL, * current;while (L != NULL){current = (struct list*)malloc(sizeof(struct list));current->data = L->data;L = L->next;current->next = newhead;newhead = current;}free(L);return newhead;
}

链表排序