目录
- 前言
- 算法题(LeetCode刷题203移除链表元素)—(保姆级别讲解)
- 算法题(LeetCode刷题707.设计链表)—(保姆级别讲解)
-
- 算法题(LeetCode刷题206.反转链表)—(保姆级别讲解)
- 算法思想(重要):
- 双指针法代码:
- 递归法(从前往后翻转指针)代码:
- 递归法(从后往前翻转指针)代码:
- 结束语
前言
本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!!
算法题(LeetCode刷题203移除链表元素)—(保姆级别讲解)
力扣题目链接
关于这个算法思想,我在之前的文章中已经提过,在这里不再赘述。
链表删除、清空和销毁-----2021-08-30
算法题(LeetCode刷题707.设计链表)—(保姆级别讲解)
力扣题目链接
关于这个算法思想,我在之前的文章中已经提过,在这里不再赘述。
链表初始化、插入、遍历功能实现----2021-08-17
链表删除、清空和销毁-----2021-08-30
代码参考:
class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
MyLinkedList() {
_dummyHead = new LinkedNode(0);
_size = 0;
}
int get(int index) {
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while(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++;
}
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++;
}
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;
};
算法题(LeetCode刷题206.反转链表)—(保姆级别讲解)
力扣题目链接
算法思想(重要):
- 双指针法
- 递归法(从前往后翻转指针)
- 递归法(从后往前翻转指针)
双指针法代码:
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp;
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
为了更能让大家了解暴力解法的算法思想,作者特意画了一张图供大家观看!!!
递归法(从前往后翻转指针)代码:
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
return reverse(NULL, head);
}
};
//可以和上面的双指针法代码进行对比参考,代码实现原理一样,这里就不再赘述了。
递归法(从后往前翻转指针)代码:
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL) return NULL;
if (head->next == NULL) return head;
ListNode *last = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return last;
}
};
为了更能让大家了解暴力解法的算法思想,作者特意画了一张图供大家观看!!!
结束语
如果觉得这篇文章还不错的话,记得点赞 ,支持下!!!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)