代码随想录算法训练营15期 Day 3 | 203.移除链表元素 、707.设计链表 、206.反转链表

链表理论基础 

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

单链表

 双链表

循环链表---可以用来解决约瑟夫环的问题 

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

链表的构造函数

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

但是上面的这个写法有点怪异，可以使用下面的这个写法

struct ListNode
{
    double value;
    ListNode *next;
    //构造函数
    ListNode(double valuel, ListNode *nextl = nullptr)
    {
        value = value1;
        next = next1;
    }
};

注意点：nullptr与NULL的区别？

①在c++98和c++03之中，NULL默认情况下被定义为无符号整型常量0,否则为无类型指针常量 (void*) 0。

#ifndef NULL
    #ifdef __cplusplus
        #define NULL 0
    #else
        #define NULL ((void *)0)
    #endif
#endif

继而下面两句的运行结果是相同的.

void test(int)
{
	cout << "test(int)" << endl;
}
 
 
int main()
{
	test(0);
	test(NULL);
	
	return 0;
}

这是因为在 C++中，字面常量 0 既可以表示一个整形常量 0，也可以表示无类型指针常量 (void*) 0，但是编译器默认把它看成是一个整形常量 0 （如果把 0 当指针使用，就必须对其进行强转 (void*) 0 ）。
由于 NULL 被定义为 0，编译器默认 NULL 就是整形常量 0，所以 test(NULL) 调用 test(int) 函数，而非 test(int*) 函数。
②在c++11出来之后,C++11标准增加了新的关键字 nullptr，保证在任何情况下都表示空指针。

void test(int)
{
	cout << "test(int)" << endl;
}
 
void test(int*)
{
	cout << "test(int*)" << endl;
}
 
int main()
{
	test(0);
	test(NULL);
	test(nullptr);
	return 0;
}

链表操作---删除节点

注意此时，D任然在内存之中，需要手动释放掉才可以。

链表操作---添加节点

链表的增添和删除都是O(1)操作，也不会影响到其他节点。要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

思路一:头结点存在可能是删除值的可能.

/**
 * 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!=nullptr && head->val == val)//while使用防止连续几个都是头结点为空
        {
            ListNode* cur = head;
            head = head->next;
            delete cur;
        }
 
        //头节点存在,并且不为空
        ListNode* cur1 = head;//注意:这个地方一定要进行相应的赋值,不能够直接操作head
        while(cur1!=nullptr && cur1->next!=nullptr)
        {
            if(cur1->next->val == val)
            {
                ListNode* tem = cur1->next;//这个地方也需要进行赋值,否则会出问题.
                cur1->next = cur1->next->next;
                delete tem;
            }
            else
            {
                cur1=cur1->next;
            }
        }
        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) {
 
        //思路二:设置虚拟头节点
        ListNode* dummynode = new ListNode(0);
        dummynode->next = head;
        //ListNode* head = dummynode;
 
        ListNode* cur = dummynode;
        while(cur->next!=nullptr)
        {
            
            if(cur->next->val == val)
            {
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
            else 
            {
                cur = cur->next;
            }
        }
       
       head=dummynode->next;
       delete dummynode;
       return head;
 
    }
};

注意:内存回收机制,C++之中存在一个delete的内存删除过程,针对于指针而言.但是java之中存在一个自动回收内存的过程.
①C++标准规定：delete空指针是合法的，没有副作用。所以我们一般在delete后就以为万事大吉了，其实这是不安全的。delete释放指针指向的那部分内存,并不是指针本身的内存,在进行delete之后,指针还是会指向那块内存,如果要没有清空,会出现***空间不能够访问的异常.

题目链接:力扣

这个地方需要注意的地方是更新边的过程,先更新哪个边.下面的代码是我自己编写的,我感觉没有错误,但是就是编译不出来,不知道啥原因.

class MyLinkedList {
public:
 
 
    //1.首先建立链表操作
    struct ListNode
    {
        int val;
        ListNode* next;
        ListNode(int val1,ListNode* next1 = nullptr)
        {
           val1 = val;
           next1 = next;
 
        }
 
    };    
    
    //2.声明大小和节点
    ListNode* dummyHead;
    int size;
    MyLinkedList() {
        dummyHead = new ListNode(0);
        size = 0;
 
    }
    
    int get(int index) {
        if(index < 0 || index >= size)
        {
            return -1;
        }
        ListNode* cur = dummyHead;
        while(index--)//直接将index进行一个减小的过程
        {
            cur = cur->next;
 
        }
        return cur->next->val;
    }
    
    void addAtHead(int val) {
        //注意头结点为空也是可以的
        ListNode* newHead = new ListNode(val);
 
        ListNode* cur = dummyHead;
 
        //注意插入的顺序,先是插入后面的元素,然后才是进行插入前面的元素
        newHead->next = cur->next;
        cur->next=newHead;
 
        //一定要注意
        size++;
 
    }
    
    void addAtTail(int val) {
 
      ListNode* newNode = new ListNode(val);
        ListNode* cur = dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        size++;
        
    }
    
    void addAtIndex(int index, int val) {
        if(index<0||index>(size-1))
        {
            return;
        }
        ListNode* cur = dummyHead;
        ListNode* newHead = new ListNode(val);
        while(index--)
        {
            cur=cur->next;
        }
        newHead->next = cur->next;
        cur=newHead;
        size++;
 
    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>(size-1))
        {
            return;
        }
        ListNode* cur = dummyHead;
        while(index--)
        {
            cur=cur->next;
        }
        ListNode* tem = cur->next;
        cur->next= cur->next->next;
        delete tem;
        tem = nullptr;
        size--;
    }
};
 
/**
 * 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* pre = nullptr;
        ListNode* cur = head;
 
        while(cur!=nullptr)
        {
            ListNode* tem= cur->next;
            cur->next=pre;
            pre=cur;
            
            cur=tem;
 
 
        }
        return pre;
 
    }
};