链表注意事项

• 链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理
• 链表的定义,需要自定义构造函数（引自代码随想录）

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

203.移除链表元素

LeetCode题目

注意事项

• 防止头指针删除带来的影响
• 删除元素之后的操作

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* subhead = new ListNode(0);
        subhead->next = head;
        ListNode* sweep = subhead;
        while (sweep->next != NULL) {
            if (sweep->next->val == val) {
                ListNode* tmp = sweep->next;
                sweep->next = sweep->next->next;
                delete tmp;
            }
            else
                sweep = sweep->next;
        }
        return subhead->next;
    }
};

707.设计链表

LeetCode题目

注意事项

• 要先定义链表，再进行使用
• 写循环时要注意的两个点：什么情况下会直接跳过循环，什么情况下结束循环，以及两者对应的处理方式
• 拼接的习惯

class MyLinkedList {
public:
    struct ListNode {
        int val;        // 节点上存储的元素
        ListNode* next; // 指向下一个节点的指针
        ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
    };

    MyLinkedList() { dummyhead = new ListNode(0); }

    int get(int index) {
        ListNode* tmp = dummyhead->next;
        if (tmp == NULL)
            return -1;
        else {
            for (int i = 0; i < index; i++) {
                if (tmp->next == NULL)
                    return -1;
                else
                    tmp = tmp->next;
            }
            return tmp->val;
        }
    }

    void addAtHead(int val) {
        ListNode* tmp = new ListNode(val);
        tmp->next = dummyhead->next;
        dummyhead->next = tmp;
    }

    void addAtTail(int val) {
        ListNode* tmp = dummyhead;
        while (tmp->next != NULL)
            tmp = tmp->next;
        ListNode* tmp1 = new ListNode(val);
        tmp1->next = tmp->next; // 感觉更规范
        tmp->next = tmp1;
    }

    void addAtIndex(int index, int val) {
        ListNode* tmp = dummyhead;
        for (int i = 0; i < index; i++) {
            if (tmp == NULL)
                break;
            else
                tmp = tmp->next;
        }
        if (tmp != NULL) {
            ListNode* tmp1 = new ListNode(val);
            tmp1->next = tmp->next;
            tmp->next = tmp1;
        }
    }

    void deleteAtIndex(int index) {
        ListNode* tmp = dummyhead;
        int i;
        for (i = 0; i < index; i++) {
            if (tmp->next == NULL) {
                i++;
                break;
            } else
                tmp = tmp->next;
        }
        if (i == index && tmp->next != NULL) {
            ListNode* tmp1 = tmp->next;
            tmp->next = tmp1->next;
            delete tmp1;
        }
    }

private:
    ListNode* dummyhead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206.反转链表

LeetCode题目

注意事项

• 反转的逻辑

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* reversehead = head;
        ListNode* pre = NULL;
        ListNode* tmp;
        while(reversehead != NULL) {
            tmp = reversehead;
            reversehead = reversehead->next;
            tmp->next = pre;
            pre = tmp;
        }
        return pre;
    }
};