江门北京网站建设,网站建设与管理论文的总结,中国建设银行上海市分行网站,网站建设大概费用文章目录链表理论基础单链表双链表循环链表其余知识点链表理论基础单链表双链表循环链表其余知识点移除链表元素习题我的解法虚拟头结点解法设计链表习题我的解法代码随想录代码反转链表习题双指针递归两两交换链表中的节点习题我的解法代码随想录解法删除链表的倒数第N个节点习…
文章目录链表理论基础单链表双链表循环链表其余知识点链表理论基础单链表双链表循环链表其余知识点移除链表元素习题我的解法虚拟头结点解法设计链表习题我的解法代码随想录代码反转链表习题双指针递归两两交换链表中的节点习题我的解法代码随想录解法删除链表的倒数第N个节点习题直观解法双指针相交链表习题题目说明暴力解法进阶解法双指针解法环形链表 II习题我的解法双指针总结链表理论基础
单链表
单链表是一种常见的线性数据结构它由一系列节点组成每个节点包含了一个数据元素和一个指向下一个节点的指针。单链表的第一个节点称为头节点最后一个节点称为尾节点尾节点的指针指向空地址。
单链表的优点是插入和删除操作比较快速时间复杂度为O(1)而查找操作则需要遍历整个链表时间复杂度为O(n)。 代码如下
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数(C11的初始化列表(initializer list)语法)
};在实现单链表时需要注意以下几点
在插入和删除节点时要注意更新链表中相邻节点的指针。在使用完节点后需要手动释放节点占用的内存以避免内存泄漏的问题。遍历链表时需要使用循环结构直到指针指向空地址。
双链表
双链表中每个节点包含了一个数据元素和两个指针分别指向前一个节点和后一个节点。双链表与单链表相比多了一个指向前一个节点的指针可以更方便地进行双向遍历和节点的插入和删除操作。 在C中可以用以下结构体定义一个双链表的结点
struct ListNode {int val; // 存储的元素值ListNode* prev; // 指向前一个节点的指针ListNode* next; // 指向后一个节点的指针ListNode(int x) : val(x), prev(nullptr), next(nullptr) {} // 构造函数
};循环链表
循环链表是一种特殊的链表它的最后一个节点的下一个节点指向第一个节点形成一个环状。循环链表可以分为单向循环链表和双向循环链表两种。
在单向循环链表中每个节点只有一个指针指向下一个节点。最后一个节点的指针指向第一个节点。
在双向循环链表中每个节点有两个指针一个指向前一个节点一个指向后一个节点。第一个节点的前一个节点指向最后一个节点最后一个节点的后一个节点指向第一个节点。 循环链表的优点是可以方便地实现循环遍历因为可以从最后一个节点回到第一个节点。同时循环链表可以解决链表中的“尾指针”问题即在链表的末尾添加节点时不需要遍历整个链表查找最后一个节点。
但是循环链表的缺点是实现起来比较复杂需要特别处理最后一个节点的指针。同时循环链表的节点数量比较难以控制容易造成内存泄漏或者死循环等问题。
以下是一个单向循环链表的结构体
struct ListNode {int val;struct ListNode *next;
};struct CircularLinkedList {ListNode *head;ListNode *tail;int size;
};其中ListNode代表链表的一个节点包含一个整数val和一个指向下一个节点的指针next。CircularLinkedList代表循环链表包含一个指向头节点的指针head、一个指向尾节点的指针tail和链表中节点的数量size。
其余知识点
删除元素如下所示 添加节点如下所示 与顺序表对比如下
链表理论基础
单链表
单链表是一种常见的线性数据结构它由一系列节点组成每个节点包含了一个数据元素和一个指向下一个节点的指针。单链表的第一个节点称为头节点最后一个节点称为尾节点尾节点的指针指向空地址。
单链表的优点是插入和删除操作比较快速时间复杂度为O(1)而查找操作则需要遍历整个链表时间复杂度为O(n)。 代码如下
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数(C11的初始化列表(initializer list)语法)
};在实现单链表时需要注意以下几点
在插入和删除节点时要注意更新链表中相邻节点的指针。在使用完节点后需要手动释放节点占用的内存以避免内存泄漏的问题。遍历链表时需要使用循环结构直到指针指向空地址。
双链表
双链表中每个节点包含了一个数据元素和两个指针分别指向前一个节点和后一个节点。双链表与单链表相比多了一个指向前一个节点的指针可以更方便地进行双向遍历和节点的插入和删除操作。 在C中可以用以下结构体定义一个双链表的结点
struct ListNode {int val; // 存储的元素值ListNode* prev; // 指向前一个节点的指针ListNode* next; // 指向后一个节点的指针ListNode(int x) : val(x), prev(nullptr), next(nullptr) {} // 构造函数
};循环链表
循环链表是一种特殊的链表它的最后一个节点的下一个节点指向第一个节点形成一个环状。循环链表可以分为单向循环链表和双向循环链表两种。
在单向循环链表中每个节点只有一个指针指向下一个节点。最后一个节点的指针指向第一个节点。
在双向循环链表中每个节点有两个指针一个指向前一个节点一个指向后一个节点。第一个节点的前一个节点指向最后一个节点最后一个节点的后一个节点指向第一个节点。 循环链表的优点是可以方便地实现循环遍历因为可以从最后一个节点回到第一个节点。同时循环链表可以解决链表中的“尾指针”问题即在链表的末尾添加节点时不需要遍历整个链表查找最后一个节点。
但是循环链表的缺点是实现起来比较复杂需要特别处理最后一个节点的指针。同时循环链表的节点数量比较难以控制容易造成内存泄漏或者死循环等问题。
以下是一个单向循环链表的结构体
struct ListNode {int val;struct ListNode *next;
};struct CircularLinkedList {ListNode *head;ListNode *tail;int size;
};其中ListNode代表链表的一个节点包含一个整数val和一个指向下一个节点的指针next。CircularLinkedList代表循环链表包含一个指向头节点的指针head、一个指向尾节点的指针tail和链表中节点的数量size。
其余知识点
删除元素如下所示 添加节点如下所示 与顺序表对比如下 移除链表元素
本节对应代码随想录中代码随想录讲解视频LeetCode203.移除链表元素_哔哩哔哩_bilibili
习题
题目链接203.移除链表元素- 力扣LeetCode
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回新的头节点。
示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5]
示例 2 输入head [], val 1 输出[]
示例 3 输入head [7,7,7,7], val 7 输出[]
我的解法
思路循环判断临时指针的下一个节点值是否等于 val等于的话就让临时指针的下一个节点指向为临时指针的下下个节点否则就让临时指针指向下一个节点(相当于遍历)。但是这种方法是判断的下一个节点因此要单独判断头结点的情况同时注意要使用 while 而不是 if因为用 if 有可能删了等于 val 的头结点下一个节点依然等于 val。
class Solution {public:ListNode* removeElements(ListNode* head, int val) {// 处理特殊情况if (head nullptr){return nullptr; }// 判断首个元素等于val的情况 while(head-val val){head head-next;// 如果head已经是nullptr说明已经没元素了,直接返回nullptrif(head nullptr){return nullptr;} }ListNode* temp head;// 判断的是temp的下一个元素,因此上面要加上判断首个元素的情况while (temp-next ! nullptr) {// 如果下一个元素值为val,则让temp的下一个元素等于下下个元素if(temp-next-valval){temp-nexttemp-next-next;}else{// 否则temp等于下一个元素(相当于遍历单链表)temp temp-next;}}return head;}
};时间复杂度O(n)。这段代码中使用了一个while循环来遍历单链表每次循环中都会判断当前节点的下一个节点是否需要删除循环的次数是单链表的长度n因此时间复杂度是O(n)。空间复杂度O(1)。这段代码中只使用了常量级别的额外空间因此空间复杂度是O(1)。
需要注意的事项
注意在 C中删除节点后要用 delete 手动删除这个节点的内存空间
虚拟头结点解法
上面我用的解法由于头结点和其余节点情况不一致(头节点前面没有元素用 next 的方式无法判断头结点)所以需要单独判断头结点。而我们可以在头结点前面加上一个虚拟节点指向头节点这样虚拟节点的 next 就指向了头节点从而实现头结点和其余节点处理逻辑达到一致。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead new ListNode(0); // 设置一个虚拟头结点dummyHead-next head; // 将虚拟头结点指向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;}
};时间复杂度O(n)。这段代码中使用了一个while循环来遍历单链表每次循环中都会判断当前节点的下一个节点是否需要删除循环的次数是单链表的长度n因此时间复杂度是O(n)。空间复杂度O(1)。这段代码中只使用了常量级别的额外空间因此空间复杂度是O(1)。
设计链表
本节对应代码随想录中代码随想录讲解视频帮你把链表操作学个通透LeetCode707.设计链表_哔哩哔哩_bilibili
习题
题目链接707. 设计链表 - 力扣LeetCode
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性val 和 next。val 是当前节点的值next 是指向下一个节点的指针/引用。如果要使用双向链表则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能
get(index)获取链表中第 index 个节点的值。如果索引无效则返回-1。addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果index小于0则在头部插入节点。deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点。
示例 MyLinkedList linkedList new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1- 2- 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1- 3 linkedList.get(1); //返回3 我的解法
题意很直接就是链表的常见操作。但刚开始写的时候不太明白 class 里面怎么放头节点看了代码随想录部分题解才明白在 class 里放一个节点的 struct 就可以。同样这题在头节点前加上一个虚拟头节点会更方便点。
注意下插入节点赋值 next 时的先后顺序如1 3中间插入2先让节点2的 next 等于节点1的 next再让节点1的 next 等于节点2。如果顺序反了的话先让节点1的 next 等于节点2这样节点2的 next 就找不到节点3了。
class MyLinkedList {public:struct Node {int val;Node* next;Node(int data) : val(data), next(nullptr) {}};// 初始化虚拟头节点设置长度为0MyLinkedList() {fakeNode new Node(0);size 0;}int get(int index) {// 虽然通过了LeetCode但这里没判断index0的情况要加上if (index 1 size) {return -1;}Node* tmp fakeNode;for (int i 0; i index 1; i) {tmp tmp-next;}// 遍历后tmp就是index位置的节点return tmp-val;}void addAtHead(int val) {Node* newNode new Node(val);// 必须先设置newNode的next否则就找不到真正的头节点了newNode-next fakeNode-next;fakeNode-next newNode;size;}void addAtTail(int val) {Node* tmp fakeNode;Node* newNode new Node(val);for (int i 0; i size; i) {tmp tmp-next;}tmp-next newNode;size;}void addAtIndex(int index, int val) {if (index size) {return;}if (index 0) {addAtHead(val);return;}Node* newNode new Node(val);Node* tmp fakeNode;for (int i 0; i index; i) {tmp tmp-next;}// 遍历后tmp位于index的前一个位置newNode-next tmp-next;tmp-next newNode;size;}void deleteAtIndex(int index) {// 还是没判断index0的情况要加上if (index 1 size) {return;}Node* tmp fakeNode;for (int i 0; i index; i) {tmp tmp-next;}// 遍历后tmp位于index的前一个位置Node* deleteNode tmp-next;tmp-next tmp-next-next;delete deleteNode; // 手动删除节点内存size--;}void printNode() {Node* tmp fakeNode;for (int i 0; i size; i) {tmp tmp-next;cout tmp-val;}}private:Node* fakeNode;int size;
};时间复杂度分析 get(int index)时间复杂度为 O(n)因为需要遍历整个链表找到 index 位置的节点。addAtHead(int val)时间复杂度为 O(1)因为只需要修改头节点的指向不需要遍历整个链表。addAtTail(int val)时间复杂度为 O(n)因为需要遍历整个链表找到尾节点并在其后面添加新节点。addAtIndex(int index, int val)时间复杂度为 O(n)因为需要遍历整个链表找到 index 位置的前一个节点并在其后面添加新节点。deleteAtIndex(int index)时间复杂度为O(n)因为需要遍历整个链表找到index位置的前一个节点并删除其后面的节点。 空间复杂度O(n)。这段代码中使用了一个结构体Node来表示单链表的节点以及一个指向虚拟头节点的指针fakeNode和一个记录链表长度的变量size。其中节点的数量和虚拟头节点的数量都是n1个因此空间复杂度是O(n)。
需要注意的点如下
注意 index 的极端情况本题我就没判断 index0的情况虽然通过了测试用例但严格意义上并不全对代码中的 size 和 fakeNode 前面加个 _ 更好如 _size 这样能和其他变量区分当然也可以用 this-size
代码随想录代码
和我的代码类似我用的 for 循环遍历他用的 while 遍历。注释已经很清晰了就不过多讲解了。
class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};// 初始化链表MyLinkedList() {_dummyHead new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点而不是真正的链表头结点_size 0;}// 获取到第index个节点数值如果index是非法数值直接返回-1 注意index是从0开始的第0个节点就是头结点int get(int index) {if (index (_size - 1) || index 0) {return -1;}LinkedNode* cur _dummyHead-next;while(index--){ // 如果--index 就会陷入死循环cur cur-next;}return cur-val;}// 在链表最前面插入一个节点插入完成后新插入的节点为链表的新的头结点void addAtHead(int val) {LinkedNode* newNode new LinkedNode(val);newNode-next _dummyHead-next;_dummyHead-next newNode;_size;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode new LinkedNode(val);LinkedNode* cur _dummyHead;while(cur-next ! nullptr){cur cur-next;}cur-next newNode;_size;}// 在第index个节点之前插入一个新节点例如index为0那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度则返回空// 如果index小于0则在头部插入节点void addAtIndex(int index, int val) {if(index _size) return;if(index 0) index 0; LinkedNode* newNode new LinkedNode(val);LinkedNode* 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;}LinkedNode* cur _dummyHead;while(index--) {cur cur -next;}LinkedNode* tmp cur-next;cur-next cur-next-next;delete tmp;_size--;}// 打印链表void printLinkedList() {LinkedNode* cur _dummyHead;while (cur-next ! nullptr) {cout cur-next-val ;cur cur-next;}cout endl;}
private:int _size;LinkedNode* _dummyHead;};时间复杂度和空间复杂度同上
反转链表
本节对应代码随想录中代码随想录讲解视频帮你拿下反转链表 | LeetCode206.反转链表 | 双指针法 | 递归法_哔哩哔哩_bilibili
习题
题目链接206. 反转链表 - 力扣LeetCode
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 输入head [1,2,3,4,5] 输出[5,4,3,2,1]
双指针
例如上面的示例我们想反转 1 2 3 4 5。用一个指针 cur 用来遍历单链表再用另一个指针 pre 指向 cur 的前面一个节点。例如 cur2时原本是1-2现在要变成2-1。直接让 cur-nextpre 就可以实现但这样的话后面的3就没法遍历到了。所以要用一个临时指针 temp 先指向 cur-next再让 cur-nextpre。
到这里就实现了1和2的反转如果想继续遍历下去还需让 pre 和 cur 都向后移一位。现在 pre、cur 和 temp 的位置为pre cur temp要让 pre 和 cur 向后移一位只要让 precurcurtemp 即可。注意这两个顺序不能颠倒否则 cur 先等于 temp那就相当于丢失了原来的 cur。
class Solution {public:ListNode* reverseList(ListNode* head) {ListNode* cur head;ListNode* pre nullptr;ListNode* tmp;while (cur ! nullptr) {tmp cur-next;cur-next pre;pre cur;cur tmp;}return pre;}
};时间复杂度O(n)。其中n为链表的长度。因为算法需要遍历整个链表时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即三个指针变量。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
递归
首先给出代码随想录上类似双指针的递归。新定义了一个函数将初始化的步骤更改为传参给新定义的函数来实现而将两个指针后移的步骤更改为调用函数递归来实现。同时和双指针的结束条件一样cur NULL 时递归函数结束。
class Solution {
public:ListNode* reverse(ListNode* pre,ListNode* cur){if(cur NULL) return pre;ListNode* temp cur-next;cur-next pre;// 可以和双指针法的代码进行对比如下递归的写法其实就是做了这两步// pre cur;// cur temp;return reverse(cur,temp);}ListNode* reverseList(ListNode* head) {// 和双指针法初始化是一样的逻辑// ListNode* cur head;// ListNode* pre NULL;return reverse(NULL, head);}};时间复杂度O(n)。其中n为链表的长度。因为算法需要遍历整个链表时间复杂度与链表长度成正比。空间复杂度O(n)。因为算法使用了递归操作递归深度最多为n层每层递归需要保存当前节点的指针以及前一个节点的指针因此空间复杂度为O(n)。
上面的递归由于和双指针的写法类似还较为容易理解而LeetCode 官方给出了更简洁的递归。
class Solution {
public:ListNode* reverseList(ListNode* head) {if (!head || !head-next) {return head;}ListNode* newHead reverseList(head-next);head-next-next head;head-next nullptr;return newHead;}
};评论区有人给出了详细的注释(java 版本)。对于 head-next-next head;如 1 2 3head2head-next33-next2相当于2-3。但是反转后2的 next 不应该再指向3了因此 head-next nullptr; 将2的 next 置为 nullptr。
public ListNode reverseList(ListNode head) {if (head null || head.next null) {/*直到当前节点的下一个节点为空时返回当前节点由于5没有下一个节点了所以此处返回节点5*/return head;}//递归传入下一个节点目的是为了到达最后一个节点ListNode newHead reverseList(head.next);/*第一轮出栈head为5head.next为空返回5第二轮出栈head为4head.next为5执行head.next.nexthead也就是5.next4把当前节点的子节点的子节点指向当前节点此时链表为1-2-3-4-5由于4与5互相指向所以此处要断开4.nextnull此时链表为1-2-3-4-5返回节点5第三轮出栈head为3head.next为4执行head.next.nexthead也就是4.next3此时链表为1-2-3-4-5由于3与4互相指向所以此处要断开3.nextnull此时链表为1-2-3-4-5返回节点5第四轮出栈head为2head.next为3执行head.next.nexthead也就是3.next2此时链表为1-2-3-4-5由于2与3互相指向所以此处要断开2.nextnull此时链表为1-2-3-4-5返回节点5第五轮出栈head为1head.next为2执行head.next.nexthead也就是2.next1此时链表为1-2-3-4-5由于1与2互相指向所以此处要断开1.nextnull此时链表为1-2-3-4-5返回节点5出栈完成最终头节点5-4-3-2-1*/head.next.next head;head.next null;return newHead;}如果还是觉得有点抽象不太好理解可以看下这个视频讲解链表反转(递归法)_哔哩哔哩_bilibili
两两交换链表中的节点
本节对应代码随想录中代码随想录讲解视频帮你把链表细节学清楚 | LeetCode24. 两两交换链表中的节点_哔哩哔哩_bilibili
习题
题目链接24. 两两交换链表中的节点 - 力扣LeetCode
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 输入head [1,2,3,4] 输出[2,1,4,3]
我的解法
由于上面的反转链表用了双指针这题我首先想到的是用双指针的解法。定义一个虚拟头节点。
对于0 1 2 3 4cur 指针指向1也就是待交换的两个节点中的第一个节点由于交换后1前面的0的 next 也会改变所以我的想法是定义第二个指针 pre 用来记录 cur 前面的节点。
定义一个临时指针等于 cur 的 next 即2然后就是1.next3、2.next1、0.next2如果不用临时指针保存2那么1.next3时就无法找到2了。
交换后顺序为0 2 1 3 4此时 pre 还是指向0cur 指向2。curcur-next 即可让 cur 遍历到下一个待交换元素的第一个位置而在这之前首先让 precur 先让 pre 前进到下一个待交换元素的前一个。
而 while 循环的终止条件每次 cur 都会指向的是待交换元素的第一个。如果是偶数个那么 cur 为 nullptr如果是奇数个那么 cur-next 为 nullptr。 一顿 next 操作后很可能就会有点迷只要记住 cur 和 pre 这些都是指针它们记录的是地址不管你再怎么 next 操作地址中的值都没发生变化。也就是说刚开始0 1 2 3 4cur 指向的是1交换操作后变成0 2 1 3 4此时 cur 指向的还是1。因此如果想让 cur 指向3只需让 curcur-next 即可。 class Solution {public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead new ListNode(0);dummyHead-next head;ListNode* pre dummyHead;//0ListNode* cur head; //1// 0 1 2 3while (cur ! nullptr cur-next ! nullptr) {ListNode* next_tmp cur-next;//2cur-next next_tmp-next;//1.next3next_tmp-next cur;//2.next1pre-next next_tmp;//0.next2pre cur;cur cur-next;}return dummyHead-next;}
};时间复杂度O(n)。其中n为链表的长度。因为算法需要遍历整个链表时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即三个指针变量和一个虚拟头节点。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
代码随想录解法
在我的解法中使用了双指针和一个临时指针变量。而在代码随想录中作者使用了一个指针两个临时指针变量。
Carl 的解法中 cur 指向的是待交换节点的前一个节点交换顺序如下图所示。执行步骤一后节点1就没法找到所以用一个临时节点记录节点1。执行步骤2后节点3就没法找到所以再用一个临时变量记录节点3。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WNQIxCg5-1679135679524)(https://code-thinking.cdn.bcebos.com/pics/24.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B91.png)]
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead new ListNode(0); // 设置一个虚拟头结点dummyHead-next head; // 将虚拟头结点指向head这样方面后面做删除操作ListNode* cur dummyHead;while(cur-next ! nullptr cur-next-next ! nullptr) {ListNode* tmp cur-next; // 记录临时节点 1ListNode* tmp1 cur-next-next-next; // 记录临时节点 3cur-next cur-next-next; // 步骤一 0.next2cur-next-next tmp; // 步骤二 2.next1cur-next-next-next tmp1; // 步骤三 1.next3cur cur-next-next; // cur移动两位准备下一轮交换}return dummyHead-next;}
};时间复杂度O(n)。其中n为链表的长度。因为算法需要遍历整个链表时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即四个指针变量和一个虚拟头节点。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
但其实这里只用一个指针就可以还是上面的例子0 1 2 3 4。Carl 的解法中 cur 指向0定义了两个临时变量分别保存1和3但其实只需要一个临时变量保存2即可。
为什么保存2可以只用一个临时变量呢我们知道转换后是0 2 1 3再看三个步骤的顺序。
1.next3、2.next1、0.next2刚好是转换后的顺序从后往前而 Carl 的顺序是从前往后。由于单链表只有向后 next 的顺序从前往后的话前面的 next 值都变了就会失去更多原有可以根据 next 找到的值。执行1.next3后由于原本2可以通过1.next 找到现在1.next3了所以就需要一个临时变量来保存2。 // cur:0
// 0 1 2 3 4
ListNode* tmp cur-next-next; // 记录临时节点2
cur-next-next tmp-next; // 步骤一 1.next3
tmp-next cur-next; // 步骤二 2.next1
cur-next tmp; // 步骤三 0.next2删除链表的倒数第N个节点
本节对应代码随想录中代码随想录讲解视频链表遍历学清楚 | LeetCode19.删除链表倒数第N个节点_哔哩哔哩_bilibili
习题
题目链接19. 删除链表的倒数第 N 个结点 - 力扣LeetCode
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cNZhXKXu-1679135703683)(null)]
输入head [1,2,3,4,5], n 2输出[1,2,3,5]输入head [1], n 1输出[]输入head [1,2], n 1输出[1]
直观解法
这道题目还挺简单的题意也很明确。需要注意的是最好使用虚拟头结点否则示例2这种就需要单独处理会麻烦一点。比较容易想到的就是既然要删倒数第 n 个节点那我们首先遍历以下链表看看总共有多少个节点然后再根据总节点数量 size 和 n 的大小遍历到待删节点的前一个节点执行删除操作即可。
这里需要注意的就是遍历的边界条件是到了待删节点的前一个节点开始执行删除操作。当遍历到待删节点本身的时候是无法进行删除的因为我们无法获得待删节点的前一个节点是什么。
class Solution {public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead new ListNode(0);dummyHead-next head;ListNode* tmp head;int size 0; // 记录链表长度// 计算链表长度while (tmp ! nullptr) {tmp tmp-next;size;}tmp dummyHead;// 找到待删除节点的前一个节点for (int i 0; i size - n; i) {tmp tmp-next;}ListNode* delNode tmp-next;tmp-next tmp-next-next;delete delNode;return dummyHead-next;}
};时间复杂度O(n)。其中n为链表的长度。因为算法需要遍历整个链表两次时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即三个指针变量和一个虚拟头节点。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
可以优化的点
今天看官方题解突然发现 ListNode* dummyHead new ListNode(0);dummyHead-next head; 这两句其实可以用 ListNode* dummyHead new ListNode(0, head); 这一句话来实现。因为 ListNode 的构造函数中有这样一句 ListNode(int x, ListNode *next) : val(x), next(next) {} 可以直接指定节点的 next不过写成两句更加直观一点。
双指针
LeetCode 上题目描述中进阶中说“你能尝试使用一趟扫描实现吗”。一开始没想出来看了题目的提示Maintain two pointers and update one with a delay of n steps.才明白。
例如0 1 2 3 4 5我们可以用一个指针 cur 来遍历用另一个指针 pre 慢 cur 指针 n1 步遍历。比如 n2时当 cur3时pre0(虚拟头结点)然后两个指针一起移动当 cur 遍历到5后面的 nullptr 时pre 刚好遍历到待删节点4的前一个节点3的位置。
如果是慢 n 步遍历那么 pre 会遍历到待删节点4的位置此时是无法执行删除节点4的操作的因此是慢 n1步。
class Solution {public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyNode new ListNode(0);dummyNode-next head;ListNode* cur dummyNode;ListNode* pre dummyNode;// cur先向前移动n1步for (int i 0; i n 1; i) {cur cur-next;}// 然后cur和pre一起向前移动while (cur ! nullptr) {cur cur-next;pre pre-next;}ListNode* delNode pre-next;pre-next pre-next-next;delete delNode;return dummyNode-next;}
};时间复杂度O(n)。其中n为链表的长度。因为算法需要遍历整个链表一次时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即三个指针变量和一个虚拟头节点。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
但是写完之后又有点疑惑这还算是一趟扫描吗因为其中有 for 循环和 while 循环。仔细琢磨后发现确实算是一趟扫描。
直观解法的解法中在第一趟扫描中需要计算链表的长度以便确定需要删除节点的前一个节点。而在第二趟扫描中才真正开始删除节点。因此这个解法需要进行两趟扫描。而双指针解法使用了两个指针来记录待删除节点的前一个节点而不需要事先计算链表的长度。
举个极端点的例子在1000个节点中我想删除倒数第1个节点即节点1000在第一个解法中需要先遍历1000个节点得知链表长度为1000然后再遍历一趟到节点999的位置执行删除操作。而在第二个解法中只需要 cur 指针先向前走2步然后 pre 指针和 cur 指针再开始一起走最后 cur 指针走到节点1000的下一个即 nullptr 时pre 刚好走到节点999的位置。在这个例子中解法一走了10019991999步而解法二只走了100121003步 为什么是1001而不是1000因为从1000走到下一步 nullptr 还需要一步 如果你还是有点不太理解看看下面的代码它没有使用 for 循环而是使用了 size 进行计数其实和上面的解法是一个意思。
class Solution {public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead new ListNode(0);dummyHead-next head;ListNode* cur dummyHead;ListNode* pre dummyHead;int size 0;while (cur ! nullptr) {// size n说明慢指针可以开始移动了if (size n)// 循环结束后pre指向待删除节点的前一个节点pre pre-next;elsesize;cur cur-next;}ListNode* delNode pre-next;pre-next pre-next-next;delete delNode;return dummyHead-next;}
};时间复杂度O(n)。其中n为链表的长度。因为算法需要遍历整个链表一次时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即三个指针变量和一个虚拟头节点。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
相交链表
本节对应代码随想录中代码随想录暂无讲解视频
习题
题目链接160. 相交链表 - 力扣LeetCode
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据保证整个链式结构中不存在环。
注意函数返回结果后链表必须保持其原始结构。
自定义评测 评测系统的输入如下你设计的程序不适用此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被视作正确答案。
示例 1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at ‘8’ 解释相交节点的值为 8 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。 在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。 — 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。
进阶你能否设计一个时间复杂度 O(m n) 、仅用 O(1) 内存的解决方案
题目说明
相信会有不少小伙伴看到题目会有点疑惑尤其是在代码随想录中跳转到的 面试题 02.07. 链表相交 - 力扣LeetCode 这个题目两个题是一样的只不过 160. 相交链表 - 力扣LeetCode的题目描述更加清楚。
上面的示例不少人刚看到会疑惑为什么相交的节点不是1而是8。注意题目中说的是节点相同示例中 A 的1和 B 的1是地址不一样只不过两个地址的数值是一样的。比如 A 中的节点1的地址0x1111而 B 中的节点1的地址为0x2222。A 中的节点4的 next 指向的是地址为0x1111的数值为1的节点而 B 中的节点6的 next 指向的是地址为0x2222的数值为1的节点。而节点8是两个链表相交的节点因为两个链表中节点8的地址是一样的。
至于怎么判断两个节点是否相同只需判断两个指针是否相同即可如 curAcurB如果你用 curA-valcurB-val 进行判断就会导致上面的例子程序输出1而不是正确答案8。
并且在本地的代码和官方的评测系统是不一样的就是说你创建了上面示例的两个链表数值相同的节点地址不一定是相同的而评测系统根据 skipA 和 skipB 参数会找到正确的结果。因此在本地运行极有可能得不到正确答案要在评测系统上提交才行。
暴力解法
这种解法简单粗暴既然要判断是否有相交的节点。那我们直接遍历链表 A 的每个节点对于每个节点分别遍历 B 中的各个节点看看是否有和当前节点相同的节点只要相同说明后续节点肯定都一样直接返回当前节点即可。 curA curB 说明节点相同并且地址也相同那么 curA 和 curB 的后续 next 肯定都相同 class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA headA;ListNode* curB headB;while(curA!nullptr){curB headB;while(curB!nullptr){if(curA curB){return curA;}curB curB-next;}curA curA-next;}return nullptr;}
};时间复杂度O(mn)。其中m和n分别为链表headA和headB的长度。因为算法需要遍历headA和headB中的所有节点时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即两个指针变量。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
进阶解法
如图如果两个链表相交那么它们的后面几个节点一定是相同的。那么我们就可以先让节点数多的那个链表向后移动两个链表节点数量的差值。在下图中就是 B 中的指针 curB 先移动到 b2位置curA 指针指向 a1然后两个指针每次都向后移动一个位置判读两个指针是否相等。当相等的时候说明节点相同返回当前指针。 代码如下大致思路就是先计算两个链表的长度然后将两个指针分别向后移动对应的步数(节点数少的移动步数为0)最后 while 循环判断指针是否相等不等就分别向后移动一个位置。
class Solution {public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {int sizeA 0, sizeB 0;ListNode* dummyHeadA new ListNode(0,headA);ListNode* dummyHeadB new ListNode(0,headB);ListNode* curA dummyHeadA;ListNode* curB dummyHeadB;// 计算两个单链表的长度循环结束后curA和curB指向的是各自链表最后一个节点while (curA-next ! nullptr) {curA curA-next;sizeA;}while (curB-next ! nullptr) {curB curB-next;sizeB;}// 如果两个链表的最后一个节点不同说明一定没有相交的节点if (curA ! curB)return nullptr;curA headA;curB headB;// 计算两个指针移动的步数int moveA sizeA sizeB ? sizeA - sizeB : 0;int moveB sizeB sizeA ? sizeB - sizeA : 0;// 两个指针分别移动各自的步数for (int i 0; i moveA; i)curA curA-next;for (int i 0; i moveB; i)curB curB-next;// 开始向后遍历当两个节点相同时则返回while (curA ! nullptr) {if (curA curB) {return curA;}curA curA-next;curB curB-next;}return nullptr;}
};时间复杂度O(mn)。其中m和n分别为链表headA和headB的长度。因为算法需要遍历headA和headB中的所有节点时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即四个指针变量和两个虚拟头节点。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
双指针解法
该双指针解法来源于 LeetCode 官方题解相交链表 - 相交链表 - 力扣LeetCode。和上面的进阶解法其实是一个思路只不过官方的题解太简洁了
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA nullptr || headB nullptr) {return nullptr;}ListNode *pA headA, *pB headB;while (pA ! pB) {pA pA nullptr ? headB : pA-next;pB pB nullptr ? headA : pB-next;}return pA;}
};时间复杂度O(mn)。其中m和n分别为链表headA和headB的长度。因为算法需要遍历headA和headB中的所有节点时间复杂度与链表长度成正比。空间复杂度O(1)。因为算法只使用了常数级别的额外空间即两个指针变量。无论输入的链表有多长算法所需的额外空间都是固定的与链表长度无关。
首先判断了特殊情况即链表 headA 或链表 headB 为空的情况如果其中一个链表为空则说明它们没有相交节点直接返回 nullptr。
接着定义了两个指针 pA 和 pB分别指向链表 headA 和链表 headB 的头节点。
然后代码进入循环判断 pA 和 pB 是否指向同一个节点如果不是则继续循环。在循环中pA 和 pB 分别向后移动一个节点如果移动到链表的末尾则将其指向另一个链表的头节点这样可以保证两个指针同时遍历链表 headA 和链表 headB直到找到相交节点或者遍历完所有节点。
最后代码返回 pA 或 pB因为它们指向的是相交节点。如果没有相交节点则返回 nullptr。
其中的 pA pA nullptr ? headB : pA-next; 可以写成如下代码
if (pA nullptr) {pA headB;
} else {pA pA-next;
}
至于为什么遍历完自己的链表后将指针指向另一个链表的头部就能同时到达相交的节点理由如下
链表 headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点链表 headB 的不相交部分有 b 个节点两个链表相交的部分有 c 个节点则有 acm bcn。
指针 pA 会遍历完链表 headA指针 pB 会遍历完链表 headB两个指针不会同时到达链表的尾节点然后指针 pA 移到链表 headB 的头节点指针 pB 移到链表 headA 的头节点然后两个指针继续移动在指针 pA 移动了 acb 次、指针 pB 移动了 bca 次之后两个指针会同时到达两个链表相交的节点该节点也是两个指针第一次同时指向的节点此时返回相交的节点。
如果链表不相交在指针 pA 移动了 mn 次、指针 pB 移动了 nm 次之后两个指针会同时变成空值 null此时返回 null。也就是说两个指针都最多走 mn 次。 理由解释来自 LeetCode 官方 举个例子链表 headA 的节点为 1 2 7 8链表 headB 的节点为 4 5 6 7 8。则 a 2,b3,c2。
PA 指向 headA 的8时PB 指向 headB 的7。然后 PA 指向 headB 的头结点级4PB 指向 headB 的8。然后 PA 指向 headB 的5PB 指向 headA 的1。然后 PA 指向 headB 的6PB 指向 headA 的2。然后 PA 指向 headB 的7PB 指向 headA 的7。两个节点相同返回 PA。
PA 走了 acb2237步PB 走了 bca3227步然后剩余的链表都还有 c2步没有走。为什么剩余的都是 c 步因为两个指针都最多走 mn 次即 acbc 步。虽然 PA 和 PB 走的顺序不一样但都把前面的 abc 走了只剩下最后的 c 步了。
环形链表 II
本节对应代码随想录中代码随想录讲解视频把环形链表讲清楚 如何判断环形链表如何找到环形链表的入口 LeetCode142.环形链表II_哔哩哔哩_bilibili
习题
题目链接142. 环形链表 II - 力扣LeetCode
给定一个链表的头节点 head 返回链表开始入环的第一个节点。如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改链表。
示例 1 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。
进阶你是否可以使用 O(1) 空间解决此题
我的解法 非最优解只是个人解法记录 我的想法是遍历每个节点并且用 now 记录虚拟头节点到当前节点的距离同时用 last 记录上一个 now 值。对于每个节点从头节点向后遍历比较 now 和 last。
当出现环的时候比如上图的3 2 0 -4cur 指向-4时虚拟头结点到-4的距离为4当遍历下一个节点即2时虚拟头结点到2的距离仅为2。也就是从虚拟头节点到当前节点的距离比到下一个节点的距离还短的时候那说明肯定出现了环并且当前节点即-4是环的最右节点而下一个节点即2是环的入口。也即是 nowlast而如果节点的下一个节点是自身那就是 nowlast所以判断条件就是 nowlast
class Solution {public:ListNode* detectCycle(ListNode* head) {ListNode* dummyHead new ListNode(0,head);ListNode* cur head;int now 0,last 0; // now记录从虚拟头节点到当前结点的距离last保存上一个now的值while(cur!nullptr){ListNode* tmp dummyHead;now 0;while(tmp!cur){tmp tmp-next;now;}// 核心语句当last值小于等于now值说明cur是环的起点if(now last){return cur;}last now; // last保存上一个now值cur cur-next;}return nullptr;}
};时间复杂度O(n^2)。这段代码的核心是两个嵌套的 while 循环外层循环遍历链表中的每个节点内层循环遍历链表中从虚拟头节点到当前节点的距离。因此总的时间复杂度为 O(n^2)。空间复杂度O(1)。这段代码只使用了常数级别的额外空间即定义了几个指针和两个整型变量因此空间复杂度为 O(1)。
但这种解法的时间复杂度为 O(n^2)并非最优解如果用哈希表来判断是否出现重复也只需要 O(n)。但由于只是想记录下自己的解法所以也写出来了算是拓展途径。由于代码随想录中的哈希表在后面章节并且此题哈希表也不是最优解因此这里就不放哈希表的解法了。
双指针
1.怎么确定是否有环
使用两个指针 fast 和 slowfast 指针每次走两步slow 指针每次走一步。如果有环那么它们一定会在环内某处相遇。
原因如果有环那么两个指针一定最后是在环内一直转圈而由于 fast 指针每次都比慢指针多走一步。可以理解成快指针每次都和慢指针的距离缩小1步那么他们之间的距离最终一定会缩减为0即相遇。
2.确定有环后怎么确定环的入口
这里就要用到数学推导了。如下图a 为头结点到环入口的距离b 为环入口到相遇点(紫色)的距离c 为相遇点到环入口的距离。那么 fast 指针走的距离 Sf an(bc)b而 slow 指针走的距离为 Ssab那么就有
Sf2Ss即 an(bc)b 2(ab)即 ac(n-1)(bc)也就是从头节点到环入口的距离刚好等于 n-1圈的环加上 c 的距离也就是说当快慢指针相遇时我们可以再定义一个指针起始点为头节点每次和 slow 指针一样也是走一步那么根据上面的式子他们一定会在环的入口相遇。 class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast head;ListNode* slow head;// 链表为空或者只有一个节点且无环时直接返回nullptrwhile(fast ! nullptr fast-next ! nullptr) {// 慢指针走一步快指针走两步slow slow-next;fast fast-next-next;// 快慢指针相遇此时从head和相遇点同时移动直至相遇if (slow fast) {ListNode* ptr head;while (ptr ! slow) {ptr ptr-next;slow slow-next;}return ptr; // 返回环的入口}}return nullptr;}
};时间复杂度O(n)。其中 n 为链表中节点的数目。在最初判断快慢指针是否相遇时slow 指针走过的距离不会超过链表的总长度随后寻找入环点时走过的距离也不会超过链表的总长度。因此总的执行时间为 O(n)O(n)O(n)。空间复杂度O(1)。我们只使用了 slowlast 和 ptr 三个指针。
总结
