[707] Design Linked List

算是基本的linked list 觀念題吧

雖說可以用雙向linked list，但我沒有覺得有太多優點XD 

因為如果加上長度的紀錄，每次要delete 或add時可以選擇從頭或從尾去找到index，

從尾巴算回來的感覺容易錯XDDD（對啦我就是廢QQ）

那就單向的開到底好了 XD 雖然比以前寫完linked list 要快了，但還是漏掉一些頭尾的特殊case啊～～～慎之。

struct Nodes {

int val;

struct Nodes *next;

};

typedef struct {

struct Nodes *head;

} MyLinkedList;

MyLinkedList* myLinkedListCreate() {

MyLinkedList *obj = calloc (1, sizeof(MyLinkedList));

obj->head= NULL;

return obj;

}

int myLinkedListGet(MyLinkedList* obj, int index) {

int count = 0;

struct Nodes *ptr = obj->head;

while (count < index && ptr != NULL)

{

count++;

ptr = ptr->next;

}

if (ptr == NULL)

return -1;

return ptr->val;

}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {

struct Nodes *ptr = calloc (1, sizeof(struct Nodes ));

ptr->val = val;

ptr->next = obj->head;

obj->head = ptr;

}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {

struct Nodes *newNode = calloc (1, sizeof(struct Nodes ));

newNode->val = val;

newNode->next = NULL;

struct Nodes *ptr = obj->head;

struct Nodes *p2=NULL;

while (ptr != NULL)

{

p2 = ptr;

ptr = ptr->next;

}

if (p2 == NULL)

obj->head = newNode;

else

p2->next = newNode;

}

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

if (index == 0)

{

myLinkedListAddAtHead(obj, val);

return;

}

int count = 0;

struct Nodes *ptr = obj->head;

struct Nodes *pre = NULL;

while (count < index)

{

count++;

if (ptr == NULL)

return;

pre = ptr;

ptr = ptr->next;

}

struct Nodes *newNode = calloc (1, sizeof(struct Nodes ));

newNode->val = val;

newNode->next = ptr;

pre->next = newNode;

return;

}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {

int count = 0;

struct Nodes *ptr = obj->head;

struct Nodes *pre = NULL;

while (count < index)

{

count++;

if (ptr == NULL)

return;

pre = ptr;

ptr = ptr->next;

}

if (ptr == NULL)

{

pre->next = NULL;

return;

}

if (pre == NULL) //head , ptr is head

obj->head= ptr->next;

else

pre->next = ptr->next;

ptr->next = NULL;

free(ptr);

return;

}

void myLinkedListFree(MyLinkedList* obj) {

struct Nodes *ptr = obj->head;

while (ptr != NULL)

{

struct Nodes *tmp = NULL;

tmp = ptr;

ptr = ptr->next;

tmp->next = NULL;

free(tmp);

}

obj->head = NULL;

free (obj->head);

free(obj);

}

/**

* 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);

*/