关于数据结构:linear-list-线性表的-链式存储方式-C语言实现

基于链式存储形式实现线性表 查问、插入、删除等操作的工夫复杂度剖析

• 按位查找、按值查找、求单链表长度工夫复杂度均为 O(n)

 设计链表的实现，在链表类中实现这些性能：get(index)：获取链表中第 index 个节点的值。如果索引有效，则返回 -1。addAtHead(val)：在链表的第一个元素之前增加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。addAtTail(val)：将值为 val 的节点追加到链表的最初一个元素。addAtIndex(index,val)：在链表中的第 index 个节点之前增加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的开端。如果 index 大于链表长度，则不会插入节点。如果 index 小于 0，则在头部插入节点。deleteAtIndex(index)：如果索引 index 无效，则删除链表中的第 index 个节点。

题目作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetb…
题目起源：力扣（LeetCode）
题解作者：WildDuck
基于链式存储形式实现线性表的代码实现

// 有头结点！有头节点！有头节点！// 链表中元素的插入为亮点设计，不须要获取待插入地位前一个元素的指针即可实现
// 以下代码在均在 Leetcode 中可执行的，带有头结点的单向链表构造

#define Elemtype int
struct MyLinkedList
{
    Elemtype val;
    struct MyLinkedList* next;
};
typedef struct MyLinkedList MyLinkedList;
//Leetcode 中服务器存储的程序主体构造间接应用了 MyLinkedList 因而须要再次重命名保障子函数能够正确执行

/** Initialize your data structure here. */
struct MyLinkedList* myLinkedListCreate()
{struct MyLinkedList* head_pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
    if (head_pointer != NULL)
    {
        head_pointer->val = 0;// 头结点值用于存储链表中元素个数！head_pointer->next = NULL;
    }
    return head_pointer;
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
// 按结点下标 get
int myLinkedListGet(struct MyLinkedList* obj, int index)
{if (index >= obj->val || index < 0)
    {return -1;}
    else
    {
        struct MyLinkedList* temp_head = obj;
        // 因为有头结点，所以多走一步
        for (int i = 0; i <= index; i++)
        {temp_head = temp_head->next;}
        return temp_head->val;
    }
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
// 附单向链表的头插法常常用于解决链表逆置问题
void myLinkedListAddAtHead(struct MyLinkedList* obj, int val)
{struct MyLinkedList* pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
    if (pointer != NULL)
    {
        pointer->val = val;
        pointer->next = NULL;
    }
    struct MyLinkedList* temp_head = obj->next;
    obj->next = pointer;
    pointer->next = temp_head;
    obj->val = obj->val + 1;
}

/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(struct MyLinkedList* obj, int val)
{struct MyLinkedList* pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
    if (pointer != NULL)
    {
        pointer->val = val;
        pointer->next = NULL;
    }

    struct MyLinkedList* temp_head = obj;
    while (temp_head->next != NULL)
    {temp_head = temp_head->next;}
    temp_head->next = pointer;
    obj->val = obj->val + 1;

}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
// 链表中元素的插入为亮点设计，不须要获取待插入地位前一个元素的指针即可实现
void myLinkedListAddAtIndex(struct MyLinkedList* obj, int index, int val)
{if (index <= 0)
    {myLinkedListAddAtHead(obj, val);
    }

    else if (index > 0 && index < obj->val)
    {
        struct MyLinkedList* temp_head = obj;
        for (int i = 0; i <= index; i++)
        {temp_head = temp_head->next;}

        struct MyLinkedList* pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
        pointer->val = temp_head->val;
        pointer->next = temp_head->next;
        temp_head->val = val;
        temp_head->next = pointer;
        obj->val = obj->val+1;
    }

    else if (index == obj->val)
    {myLinkedListAddAtTail(obj, val);
    }
}

/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(struct MyLinkedList* obj, int index)
{
    // 按下标删除，index 不可能大于元素个数
    if (index < obj->val && index >= 0)
    {
        struct MyLinkedList* temp_head = obj;
        struct MyLinkedList* temp_next = NULL;
        // 找到 index 之前的一个元素
        for (int i = 0; i < index; i++)
        {temp_head = temp_head->next;}
        temp_next = temp_head->next->next;

        if (temp_head->next != NULL) free(temp_head->next);
        temp_head->next = temp_next;
        obj->val = obj->val-1;
    }
}

void myLinkedListFree(struct MyLinkedList* obj)
{
    struct MyLinkedList* temp_head = obj;
    struct MyLinkedList* temp_free = NULL;

    while (temp_head->next!=NULL)
    {
        temp_free = temp_head;
        temp_head = temp_head->next;
        free(temp_free);
    }

}

附经典问题链表逆置——头插法解决链表逆置问题：

留神要点和原理

// 迭代模式解决问题
struct ListNode* AddAtHead(struct ListNode* source,struct ListNode* new_head)
{
    struct ListNode* pointer = new_head->next;
    new_head->next = source;
    source->next = pointer;
    return new_head;
}

struct ListNode* reverseList(struct ListNode* head){struct ListNode* new_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    // 此为虚伪头，最初须要被开释、挪动指针再返回
    new_head->next = NULL;
    struct ListNode* temp_head = head;
    struct ListNode* temp_next = NULL;
    while (temp_head != NULL)
    {
        temp_next = temp_head->next;
        new_head = AddAtHead(temp_head,new_head);
        temp_head = temp_next;
    }
    temp_head = new_head;
    head = new_head->next;
    free(temp_head);
    return head;
}