力扣：707. 設(shè)計鏈表
題目：
??
707. 設(shè)計鏈表
你可以選擇使用單鏈表或者雙鏈表，設(shè)計并實現(xiàn)自己的鏈表。
單鏈表中的節(jié)點應(yīng)該具備兩個屬性：val?和?next?。val?是當(dāng)前節(jié)點的值，next?是指向下一個節(jié)點的指針/引用。
如果是雙向鏈表，則還需要屬性?prev?以指示鏈表中的上一個節(jié)點。假設(shè)鏈表中的所有節(jié)點下標(biāo)從?0?開始。
實現(xiàn)?MyLinkedList?類：
MyLinkedList()?初始化?MyLinkedList?對象。int get(int index)?獲取鏈表中下標(biāo)為?index?的節(jié)點的值。如果下標(biāo)無效，則返回?-1?。void addAtHead(int val)?將一個值為?val?的節(jié)點插入到鏈表中第一個元素之前。在插入完成后，新節(jié)點會成為鏈表的第一個節(jié)點。void addAtTail(int val)?將一個值為?val?的節(jié)點追加到鏈表中作為鏈表的最后一個元素。void addAtIndex(int index, int val)?將一個值為?val?的節(jié)點插入到鏈表中下標(biāo)為?index?的節(jié)點之前。如果?index?等于鏈表的長度，那么該節(jié)點會被追加到鏈表的末尾。如果?index?比長度更大，該節(jié)點將?不會插入?到鏈表中。void deleteAtIndex(int index)?如果下標(biāo)有效，則刪除鏈表中下標(biāo)為?index?的節(jié)點。
?
示例：
輸入["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); ? ?// 鏈表變?yōu)?1->2->3 myLinkedList.get(1); ? ? ? ? ? ? ?// 返回 2 myLinkedList.deleteAtIndex(1); ? ?// 現(xiàn)在，鏈表變?yōu)?1->3 myLinkedList.get(1); ? ? ? ? ? ? ?// 返回 3
?
提示：
0 <= index, val <= 1000請不要使用內(nèi)置的 LinkedList 庫。
調(diào)用?
get、addAtHead、addAtTail、addAtIndex?和?deleteAtIndex?的次數(shù)不超過?2000?。
注意：
不要粗心操作空指針，如果要將鏈表的下一個值賦給一個指針，并需要使用這個指針要注意會不會是一個空指針
在某個特定的序號上做操作可以讓循環(huán)一直進行，用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);
*/
