您现在的位置是：首页 >学无止境 >算法训练营第三天|链表理论基础 、 203.移除链表元素 、 707.设计链表 、 206.反转链表网站首页学无止境

1.链表理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

链表分为单链表、双链表和循环链表

如图所示： 

 如图所示： 

 链表的存储方式：逻辑空间连续，物理空间不连续。

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

//不写构造函数的话也有默认构造，但是初始化节点时候有区别
ListNode* head = new ListNode(5);//通过自己定义构造函数初始化节点

ListNode* head = new ListNode();//使用默认构造函数初始化节点
head->val = 5;

//所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

删除节点：

如图所示：

只要将C节点的next指针 指向E节点就可以了。

添加节点：

如图所示：

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

再把链表的特性和数组的特性进行一个对比，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

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* flasenode = new ListNode(0,head);//该节点值为0，指向head节点
        //创建一个移动指针,指向头节点
        ListNode* cur = flasenode;
        while(cur->next!=nullptr){
            if(cur->next->val == val){
                //创建一个临时节点用来存储要删除的节点
                ListNode* tem = cur->next;
                cur->next = cur->next->next;
                delete tem;
            }else{
                //移动cur指针
                cur = cur->next;
            }

        }
        //都循环完了 重新命名头节点
        head = flasenode->next;
        delete flasenode;
        return head;
    }
};

注意结点的创建

原始方法：

/**
 * 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) {
        //传统解法不添加虚拟头节点
        //头节点和中间节点分开处理

        //先考虑头节点情况
        while(head!=NULL&&head->val == val){
            ListNode* tem = head;//不写临时节点也能通过提交
            head = head->next;
            delete tem;//不释放原来内存也可以提交
        }
        ListNode* cur = head;
        while(cur!=NULL&&cur->next != NULL){
            if(cur->next->val == val){
                ListNode* tem = cur->next;
                cur->next = cur->next->next;
                delete tem;
            }else{
                cur = cur->next;
            }
            
        }
        return head;

    }
};

头节点和非头节点分开处理，代码比较长，还是统一处理比较好

class MyLinkedList {
public:
    struct LinkedNode{
        int val;
        LinkedNode* next;
        //定义一个节点构造函数
        LinkedNode(int val):val(val),next(nullptr){

        }

    };
    MyLinkedList() {
        flasenode = new LinkedNode(0);
        size = 0;
        
    }
    
    int get(int index) {
        if(index < 0 || index > (size-1)){
            return -1;
        }
        LinkedNode* cur = flasenode->next;
        while(index){
            cur = cur->next;
            index--;
        }
        return cur->val;


    }
    
    void addAtHead(int val) {
        LinkedNode* newnode = new LinkedNode(val);
        // LinkedNode* cur = flasenode->next;
        newnode->next = flasenode->next;
        flasenode->next = newnode;

        size++;//注意size要+1操作


    }
    
    void addAtTail(int val) {
        LinkedNode* newnode = new LinkedNode(val);
        LinkedNode* cur = flasenode;//但凡涉及到遍历元素，都要创建一个新指针指向
        while (cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newnode;
        size++;
       
    }
    
    void addAtIndex(int index, int val) {
        if( index > (size)){
            return;
        }
        if(index < 0) index = 0;
        LinkedNode* newnode = new LinkedNode(val);
        LinkedNode* cur = flasenode;
        while(index--){
            cur = cur->next;
        }
        newnode->next = cur->next;
        cur->next = newnode;
        size++;

    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index > size-1){
            return;
        }
        LinkedNode* cur = flasenode;
        while(index--){
            cur = cur->next;
        }
        LinkedNode* tem = cur->next;
        cur->next = cur->next->next;
        delete tem;
        size--;

    }
private:
    int size;
    LinkedNode* flasenode;
};

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

/**
 * 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* cur = head;
        ListNode* pre = nullptr;
        while(cur != nullptr){
            ListNode* tem = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tem;
        }
        return pre;

    }
};

/**
 * 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) {
        return reverse(head,nullptr);

    }
    ListNode* reverse(ListNode* cur,ListNode* pre){
        //终止条件
        if (cur == nullptr) {
            return pre;
        }
        ListNode* tem = cur->next;
        cur->next = pre;
        return reverse(tem,cur);
    }
};