卖信息的网站,溧阳市住房和城乡建设局网站,网站建设需要写代码吗,百度地图开放平台刷题的第三天#xff0c;希望自己能够不断坚持下去#xff0c;迎来蜕变。#x1f600;#x1f600;#x1f600; 刷题语言#xff1a;C / Python Day3 任务 ● 链表理论基础 ● 203.移除链表元素 ● 707.设计链表 ● 206.反转链表
1 链表理论基础
链表#xff1a;通过…刷题的第三天希望自己能够不断坚持下去迎来蜕变。 刷题语言C / Python Day3 任务 ● 链表理论基础 ● 203.移除链表元素 ● 707.设计链表 ● 206.反转链表
1 链表理论基础
链表通过指针串联在一起的线性结构每个节点由指针域和数据域组成。 指针域存放指向下一个节点的指针最后一个节点的指针域指向null 数据域节点存放着数据
1链表的类型
单链表 每个节点的指针域指向下一个节点 双链表 每一个节点有两个指针域一个指向下一个节点一个指向上一个节点 可以双向查询 循环链表 链表首尾相连可以用来解决约瑟环问题
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, nextNone):self.val valself.next next4链表的操作
删除节点 将C节点的指针指向E就间接删除了DC需要自己手动释放内存Python不需要自己手动释放内存 添加节点 C节点指向新节点新节点指向D节点就完成了在C和D节点之间插入了新节点。 5链表与数组的区别
数组在定义的时候长度是固定的如果需要改变数组的长度需要重新定义一个新的数组链表的长度可以是不固定的动态增删适合数据量不固定频繁增删少查询的场景
插入/删除查询适用场景数组O(n)O(1)数据量固定频繁查询较少插入和删除的场景链表O(1)O(n)数据量不固定较少查询频繁插入和删除的场景
2 移除链表元素 C编程语言需要自己手动删除清理节点的内存 Python就不用手动管理内存了 因为单链表的特殊性只能指向下一个节点如果删除的是头节点怎么办如何让头节点的前一个节点指向头节点的下一个节点。 有两种处理方式 1直接使用原来的链表进行删除操作分两步操作1.删除头节点2.删除除了头节点的其他节点 只要将头结点向后移动一位就可以这样就从链表中移除了一个头结点依然别忘将原头结点从内存中删掉 2设置一个虚拟头节点进行删除操作 原链表的所有节点就都可以按照统一的方式进行移除了 直接使用原来的链表来进行移除节点操作
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: ListNodewhile 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
设置一个虚拟头结点在进行移除节点操作
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, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def removeElements(self, head, val)::type head: ListNode:type val: int:rtype: ListNodedummyhead ListNode(next head)cur dummyheadwhile cur.next:if cur.next.val val:cur.next cur.next.nextelse:cur cur.nextreturn dummyhead.next3 设计链表 实现 MyLinkedList 类
class MyLinkedList
{};链表定义
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};定义两个私有成员
private:int _size;ListNode* _dummyhead; // 虚拟头节点MyLinkedList() 初始化 MyLinkedList 对象。
MyLinkedList()
{_dummyhead new ListNode(0);_size 0;
}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;
}void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点。
void addAtHead(int val) {ListNode* newNode new ListNode(val);newNode-next _dummyhead-next;_dummyhead-next newNode;_size;
}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;
}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;
}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: ListNodecur headpre Nonewhile cur ! None:tmp cur.nextcur.next prepre curcur tmpreturn pre时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) 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)今天真是搞了不少时间鼓励坚持三天的自己
