Leetcode 707 -- 设计链表

1. 题目描述

设计一个链表，实现基本操作(增删改查)

2. 单链表

/*============================================
            some instructinos:

pre   : leetcode's List always define as follows
type  : this link is single Link with head node

struct ListNode{
    int val;
    struct ListNode *next;
};  
============================================*/

#define MAX(a,b) (((a)>(b)) ? (a) : (b))

typedef struct {
    struct ListNode *head;
    int size; // Link_length
} MyLinkedList;

/*============================================*/

struct ListNode* ListNodeCreate(int val)
{ 
    // you should ues : sizeof(struct ListNode)
    // but            : sizeof struct ListNode
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

MyLinkedList* myLinkedListCreate() {
    MyLinkedList *L = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    // there we only alloc memory for myLinkedList
    // but we not alloc memory for myLinkedList->head !!!
    // it's very easy to forget to malloc it and get bug that very difficult to debug
    L->head = ListNodeCreate(0);
    L->size = 0;
    return L;
}


/*============================================*/

int myLinkedListGet(MyLinkedList* L, int index) {
    int length = L->size;
    if(length == 0 || index < 0 || index >= length) return -1;
    
    struct ListNode *cur = L->head->next;
    for(int i = 0; i < index; i ++ )    cur = cur->next;
    return cur->val;
}

/*============================================*/


void myLinkedListDeleteAtIndex(MyLinkedList* L, int index) {
    int length = L->size;
    if(length == 0 || index < 0 || index >= length) return ;
    
    struct ListNode *prev = L->head;
    for(int i = 0; i < index; i ++ )    prev = prev->next;
    struct ListNode *delNode = prev->next;
    prev->next = prev->next->next;
    free(delNode);
    L->size -- ;
}

void myLinkedListFree(MyLinkedList* L) {
    struct ListNode *cur = L->head;   
    // head node also have memory
    // so we have to should to free it
    while(cur)
    {
        struct ListNode *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    free(L);
}

/*============================================*/

// index start from 0
void myLinkedListAddAtIndex(MyLinkedList* L, int index, int val) {
    int length = L->size;
    
    // special check at first
    if(index > length) return ;
    
    // if index < 0 then index is assignmented as 0, can reduce if check
    index = MAX(0, index); 
    
    // get prev node
    struct ListNode *prev = L->head;
    for(int i = 0; i < index; i ++ )    prev = prev->next;
    
    // add new node
    struct ListNode *newNode = ListNodeCreate(val);
    newNode->next = prev->next;
    prev->next = newNode;
    L->size ++ ;
}

void myLinkedListAddAtHead(MyLinkedList* L, int val) {
    myLinkedListAddAtIndex(L, 0, val); // completee by myLinkedListAddAtIndex
}

void myLinkedListAddAtTail(MyLinkedList* L, int val) {
    myLinkedListAddAtIndex(L, L->size, val);        // complete by myLinkedListAddAtIndex
}


/*============================================*/


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

3. 双链表

4. bug