数据结构与算法

动态数组: 开辟销毁内存空间的次数相对比较少, 但可能造成内存空间浪费;
双向链表: 开辟销毁内存空间的次数相对较多, 但不会造成内存空间浪费.

1. 链表翻转
   面试题24. 反转链表

// O(n)
struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *newHead = NULL;
    while (head) {
        struct ListNode *temp = head->next;
        head->next = newHead;
        newHead = head;
        head = temp;
    }
    return newHead;
}

// 递归 - O()
struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;

    return newHead;
}

2. 快慢指针
   141. 环形链表

bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    while (fast && fast->next) {
        if (slow == fast) {
            return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

3. 删除链表中的节点

void deleteNode(struct ListNode* node) {
    node->val = node->next->val;
    node->next = node->next->next;
}

4. 203. 移除链表元素

// 哨兵节点法
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode *sentinelNode = malloc(sizeof(struct ListNode));
    sentinelNode->next = head;
    struct ListNode *curr = head;
    struct ListNode *prev = sentinelNode;

    while (curr) {
        if (curr->val == val) {
            prev->next = curr->next;
        } else {
            prev = curr;
        }
        curr = curr->next;
    }

    return sentinelNode->next;
}

5. 83. 删除排序链表中的重复元素

struct ListNode * deleteDuplicates(struct ListNode* head) {
    struct ListNode *sential = malloc(sizeof(struct ListNode));
    sential->next = head;

    struct ListNode *pre = sential;
    struct ListNode *curr = head;

    while (curr && curr->next) {
        if (curr->val == curr->next->val) {
            pre->next = curr->next;
        } else {
            pre = curr;
        }
        curr = curr->next;
    }
    return sential->next;
}

栈(stack)
LIFO(last in first out)
push pop

队列(queue)
FIFO - 基于双向列表实现