题目：

707. 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val和 next。val是当前节点的值，next是指向下一个节点的指针/引用。

【资料图】

如果是双向链表，则还需要属性 prev以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList类：

MyLinkedList()初始化 MyLinkedList对象。

int get(int index)获取链表中下标为 index的节点的值。如果下标无效，则返回 -1。

void addAtHead(int val)将一个值为 val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

void addAtTail(int val)将一个值为 val的节点追加到链表中作为链表的最后一个元素。

void addAtIndex(int index, int val)将一个值为 val的节点插入到链表中下标为 index的节点之前。如果 index等于链表的长度，那么该节点会被追加到链表的末尾。如果 index比长度更大，该节点将 不会插入 到链表中。

void deleteAtIndex(int index)如果下标有效，则删除链表中下标为 index的节点。

示例：

输入["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"][[], [1], [3], [1, 2], [1], [1], [1]]输出[null, null, null, null, 2, null, 3]解释MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.addAtHead(1);myLinkedList.addAtTail(3);myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3myLinkedList.get(1);              // 返回 2myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3myLinkedList.get(1);              // 返回 3

提示：

0 <= index, val <= 1000

请不要使用内置的 LinkedList 库。

调用 get、addAtHead、addAtTail、addAtIndex和 deleteAtIndex的次数不超过 2000。

注意：

不要粗心操作空指针，如果要将链表的下一个值赋给一个指针，并需要使用这个指针要注意会不会是一个空指针

在某个特定的序号上做操作可以让循环一直进行，用if语句来判断指针是否到达要操作的地方。

第一种对法：

typedef struct MyLinkedList{

int val;

struct MyLinkedList *next;

} MyLinkedList;

MyLinkedList* myLinkedListCreate() {

MyLinkedList *head = (MyLinkedList *)malloc(sizeof(MyLinkedList));

head->next = NULL;

return head;

}

int myLinkedListGet(MyLinkedList* obj, int index) {

MyLinkedList *cur = obj->next;

for(int i=0;cur!=NULL;i++){

if(i==index){

return cur->val;

}else{

cur=cur->next;

}

}

return -1;

}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {

MyLinkedList *nhead = (MyLinkedList *)malloc(sizeof(MyLinkedList));

nhead->val = val;

nhead->next = obj->next;

obj->next = nhead;

}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {

MyLinkedList *ntail = (MyLinkedList*)malloc(sizeof(MyLinkedList));

MyLinkedList *cur = obj;

ntail->val = val;

ntail->next = NULL;

while(cur->next!=NULL)cur = cur->next;

cur->next = ntail;

}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {

MyLinkedList *newnode = (MyLinkedList *)malloc(sizeof(MyLinkedList));

newnode->val = val;

if(index==0){

newnode->next = obj->next;

obj->next = newnode;

return;

}

MyLinkedList *cur = obj->next;

for(int i=1;cur!=NULL;i++){

if(i==index){

newnode->next = cur->next;

cur->next=newnode;

return;

}else{

cur=cur->next;

}

}

}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {

MyLinkedList *cur=obj;

MyLinkedList *tmp;

for(int i=0;cur!=NULL&&cur->next!=NULL;i++){

if(index==i){

tmp = cur->next;

cur->next = tmp->next;

free(tmp);

return;

}else{

cur=cur->next;

}

}

}

void myLinkedListFree(MyLinkedList* obj) {

MyLinkedList *tmp;

while(obj!=NULL){

tmp = obj;

obj=obj->next;

free(tmp);

}

return;

}

/**

* Your MyLinkedList struct will be instantiated and called as such:

* MyLinkedList* obj = myLinkedListCreate();

* int param_1 = myLinkedListGet(obj, index);

* myLinkedListAddAtHead(obj, val);

* myLinkedListAddAtTail(obj, val);

* myLinkedListAddAtIndex(obj, index, val);

* myLinkedListDeleteAtIndex(obj, index);

* myLinkedListFree(obj);

*/

关键词：