链表的常见操作-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表的常见操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链表

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;
        else
            pre->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函数开辟的空间中，不要进行指针的移动，因为一旦移动之后可能出现申请的空间和释放空间大小的不匹配文章来源地址https://www.toymoban.com/news/detail-804618.html

循环链表

单独创建

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;
        else
            pre->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;
            else
                pre->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;
            else
                newpre->next = newcurrent;
            newcurrent->data = (*L)->data;
            newcurrent->next = NULL;
            newpre = newcurrent;
            
            if((*L) == newL)
                newL = newL->next;
            else
                pre-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;
}