代码随想录刷题题Day3

刷题的第三天，希望自己能够不断坚持下去，迎来蜕变。😀😀😀
刷题语言：C++ / Python
Day3 任务
● 链表理论基础
● 203.移除链表元素
● 707.设计链表
● 206.反转链表

1 链表理论基础

链表：通过指针串联在一起的线性结构，每个节点由指针域和数据域组成。
指针域：存放指向下一个节点的指针，最后一个节点的指针域指向null
数据域：节点存放着数据

（1）链表的类型

1. 单链表
   每个节点的指针域指向下一个节点
   
2. 双链表
   每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点

可以双向查询

3. 循环链表
   链表首尾相连，可以用来解决约瑟环问题
   

（2）链表的存储方式
链表在内存中不是连续分布的（区别于数组）

通过指针域的指针链接内存中的各个节点，散乱分布在内存的某地址上，分配机制取决于操作系统的内存管理

（3）链表的定义
C++的定义链表节点方式

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

如果不自己定义构造函数初始化节点：

ListNode* head = ListNode();
head->val = 5;

采用上面自己定义的构造函数初始化节点可以直接给变量赋值：

ListNode* head = ListNode(5);

Python的定义链表节点方式

class ListNode:def __init__(self, val, next=None):self.val = valself.next = next

（4）链表的操作

1. 删除节点
   

将C节点的指针指向E，就间接删除了D，C++需要自己手动释放内存，Python不需要自己手动释放内存

2. 添加节点
   

C节点指向新节点，新节点指向D节点，就完成了在C和D节点之间插入了新节点。

（5）链表与数组的区别

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

	插入/删除	查询	适用场景
数组	O(n)	O(1)	数据量固定，频繁查询，较少插入和删除的场景
链表	O(1)	O(n)	数据量不固定，较少查询，频繁插入和删除的场景

2 移除链表元素

C++编程语言需要自己手动删除清理节点的内存
Python就不用手动管理内存了

😀因为单链表的特殊性，只能指向下一个节点，如果删除的是头节点怎么办？如何让头节点的前一个节点指向头节点的下一个节点。

有两种处理方式：
（1）直接使用原来的链表进行删除操作：分两步操作1.删除头节点2.删除除了头节点的其他节点

只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点，依然别忘将原头结点从内存中删掉

（2）设置一个虚拟头节点进行删除操作 ： 原链表的所有节点就都可以按照统一的方式进行移除了

1. 直接使用原来的链表来进行移除节点操作
   

C++:

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 删除头节点while (head != NULL && head->val == val){ListNode* tmp = head;head = head->next; // 让下一个节点作为头节点delete tmp;}// 删除非头节点ListNode* cur = head;while (cur != NULL && cur->next != NULL){if (cur->next->val == val){ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;}else{cur = cur->next;}}return head;}
};

Python:

class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""while head != None and head.val == val:head = head.nextcur = headwhile cur != None and cur.next != None:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn head

2. 设置一个虚拟头结点在进行移除节点操作
   

C++:

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

Python:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""dummyhead = ListNode(next = head)cur = dummyheadwhile cur.next:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dummyhead.next

3 设计链表

实现 MyLinkedList 类：

class MyLinkedList 
{};

链表定义：

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

定义两个私有成员：

private:int _size;ListNode* _dummyhead; // 虚拟头节点

1. MyLinkedList() 初始化 MyLinkedList 对象。

MyLinkedList()
{_dummyhead = new ListNode(0);_size = 0;
}

2. int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。

int get(int index) {if (index < 0 || index > size - 1) return -1;ListNode* cur = _dummyhead->next;while (index--){cur = cur->next;}return cur->val;
}

3. void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

void addAtHead(int val) {ListNode* newNode = new ListNode(val);newNode->next = _dummyhead->next;_dummyhead->next = newNode;_size++;
}

4. void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。

void addAtTail(int val) {ListNode* cur = _dummyhead;ListNode* newNode = new ListNode(val);while (cur->next != NULL){cur = cur->next;}cur->next = newNode;_size++;
}

5. void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。

void addAtIndex(int index, int val) {if (index < 0) index = 0;if (index > _size) return;ListNode* newNode = new	ListNode(val);ListNode* cur = _dummyhead;while (index--){cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;
}

6. void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

void deleteAtIndex(int index) {if (index < 0 || index >= _size) return;ListNode* cur = _dummyhead;while (index--){cur = cur->next;}ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = NULL;_size--;
}

C++:

class MyLinkedList {
public:
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};MyLinkedList() {_dummyhead = new ListNode(0); // 虚拟头结点_size = 0;}// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点int get(int index) {if (index < 0 || index > _size - 1) return -1;ListNode* cur = _dummyhead->next;while (index--)// 如果--index 就会陷入死循环{cur = cur->next;}return cur->val;}// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点void addAtHead(int val) {ListNode* newNode = new ListNode(val);newNode->next = _dummyhead->next;_dummyhead->next = newNode;_size++;}// 在链表最后面添加一个节点void addAtTail(int val) {ListNode* newNode = new ListNode(val);ListNode* cur = _dummyhead;while(cur->next != NULL){cur = cur->next;}cur->next = newNode;_size++;}void addAtIndex(int index, int val) {if (index < 0) index = 0; // 如果index小于0，则在头部插入节点if (index > _size) return; // 如果index大于链表的长度，则返回空ListNode* newNode = new ListNode(val);ListNode* cur = _dummyhead;while (index--){cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的void deleteAtIndex(int index) {if (index >= _size || index < 0) return;ListNode* cur = _dummyhead;while (index--){cur = cur->next;}ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = NULL;_size--;}
private:int _size;ListNode* _dummyhead;
};

4 反转列表

（1）双指针
只需要改变链表的next指针的指向，直接将链表反转


伪代码：

cur = head;
pre = NULL;
// 移动pre和cur指针 注意下面的逻辑顺序
while (cur != NULL)
{tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;
}
return pre; // 返回头节点

C++:

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = NULL;while (cur != NULL){ListNode* tmp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur->next = pre;// 翻转// 更新pre 和 cur指针pre = cur;cur = tmp;}return pre;}
};

Python:

class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""cur = headpre = Nonewhile cur != None:tmp = cur.nextcur.next = prepre = curcur = tmpreturn pre

时间复杂度：$O(n)$
空间复杂度：$O(1)$
（2）递归
相对抽象,和双指针法是一样的逻辑
C++:

class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur){if (cur == NULL) return pre;ListNode* tmp = cur->next;cur->next = pre;// pre = cur;// cur = temp;return reverse(cur, temp);}ListNode* reverseList(ListNode* head) {// 和双指针法初始化是一样的逻辑reverse(NULL, head);}
};

Python:

class Solution(object):def reverseList(self, head):return self.reverse(head,None)def reverse(self, cur, pre):if cur == None:return pretmp = cur.nextcur.next = prereturn self.reverse(tmp, cur)

---

今天真是搞了不少时间，鼓励坚持三天的自己😀😀😀