Leetcode 刷题第三天|链表

链表理论

什么是链表

链表是一种通过指针串联在一起的线性结构，每个节点有两个部分组成：数据域和指针域。最后一个节点的指针域指向null
链表的入口节点为链表的头结点也就是head。
链表结构示意图

链表的类型

单链表

如上图就是单链表

双链表

单链表的指针域只有一个，指向下一个节点。
双链表的指针域有两个，一个指向下一个节点，另一个指向上一个节点。
在这里插入图片描述

循环链表

循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来表示约瑟夫环问题。
在这里插入图片描述

链表的存储方式

了解完链表的类型，再说一下链表的存储方式。
数组是再内存中连续分布的，而链表在内存中则不是连续分布的，
链表可以通过指针域访问内存中中不连续的某个节点。
在这里插入图片描述

链表的定义

接下来说一下链表的定义
下面的是C/C++的定义的链表节点，如下所示。

struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {} 
};

链表的操作

删除节点

删除D节点如下图，
在这里插入图片描述
只要将C节点的next指向E就可以了。
在C++ 中需要将D节点手动释放掉。

添加节点

在这里插入图片描述

性能分析

在这里插入图片描述

203. 移除链表元素

/**
 * 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* removeElements(ListNode* head, int val) {
        ListNode* p = new ListNode(0, head);
        ListNode* cur = p->next;
        ListNode* front = p;
        while(cur) {
            if(cur->val == val) {
                front->next = cur->next;
                cur = cur->next;
            }else {
                front = cur;
                cur = cur->next;
            }
        }
        return p->next;
    }
};

707 设计链表

class MyLinkedList {
public:
    MyLinkedList() {
        phead = new ListNode(0);
    }
    
    int get(int index) {
        ListNode* p = phead->next;
        while(index) {
            p = p->next;
            index--;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val, phead->next);
        phead->next = newNode;
    }
    
    void addAtTail(int val) {
        ListNode* cur = phead->next;
        ListNode* fNode = phead;
        while(cur) {
            fNode = cur;
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val);
        fNode->next =newNode;
    }
    
    void addAtIndex(int index, int val) {
        ListNode* cur = phead->next;
        ListNode* fNode = phead;
        while(index) {
            index--;
            fNode = cur;
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val, cur);
        fNode->next = newNode;
        return;
    }
    
    void deleteAtIndex(int index) {
        ListNode* cur = phead->next;
        ListNode* fNode = phead;
        while(index) {
            index--;
            fNode = cur;
            cur = cur->next;
        }
        ListNode* nextNode = cur->next;
        fNode->next = nextNode;
    }
    private:
    ListNode* phead;
};

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

本地测试没问题，但是提交会有问题。
在这里插入图片描述
本地测试的用例通过了，但是提交上去报这个错误。抓耳挠腮

class MyLinkedList {
public:
    MyLinkedList() {
        phead = new ListNode(0);
    }
    
    int get(int index) {
        ListNode* p = phead;
        while(index) {
            p = p->next;
            index--;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val, phead->next);
        phead->next = newNode;
    }
    
    void addAtTail(int val) {
        ListNode* cur = phead;
        ListNode* fNode = phead;
        while(cur) {
            fNode = cur;
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val);
        fNode->next =newNode;
    }
    
    void addAtIndex(int index, int val) {
        ListNode* cur = phead;
        ListNode* fNode = phead;
        while(index) {
            index--;
            fNode = cur;
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val, cur->next);
        fNode->next = newNode;
        return;
    }
    
    void deleteAtIndex(int index) {
        ListNode* cur = phead;
        ListNode* fNode = phead;
        while(index) {
            index--;
            fNode = cur;
            cur = cur->next;
        }
        fNode->next = cur->next;
        delete cur;
    }
    private:
    ListNode* phead;
};

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