「代码随想录算法训练营」第三天 | 链表 part1
203.移除链表元素
题目链接：https://leetcode.cn/problems/remove-linked-list-elements/
题目难度：简单
文章讲解：https://programmercarl.com/0203.移除链表元素.html
视频讲解： https://www.bilibili.com/video/BV18B4y1s7R9
题目状态：通过
个人思路：
从链表头部开始依次往下遍历，当遇到和val值相等的元素就将其移除（walk->next = walk->next->next），最后返回修改后的链表。
遇到的问题：
- 直接将遍历指针
walk初始化在了链表头，没能考虑到头节点就是需要移除的节点的情况。 - 采用 C++ 编写代码的时候，忘记要从内存中删除移除的节点，清理节点内存。
最终代码如下：
/**
* 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)
{
head = head->next;
}
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode* walk = dummy;
while(walk->next != nullptr)
{
if(walk->next->val == val)
{
ListNode *tmp = walk->next;
walk->next = tmp->next;
delete tmp;
}
else
{
walk = walk->next;
}
}
ListNode *newHead = dummy->next;
delete dummy;
return newHead;
}
};
707.设计链表
题目链接：https://leetcode.cn/problems/design-linked-list/
题目难度：中等
文章讲解：https://programmercarl.com/0707.设计链表.html
视频讲解： https://www.bilibili.com/video/BV1FU4y1X7WD
题目状态：思路混乱，看卡哥代码
最终代码如下：
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 || 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 *cur = _dummyHead;
LinkedNode *newNode = new LinkedNode(val);
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 = tmp->next;
delete tmp;
tmp = nullptr;
_size--;
}
private:
int _size;
LinkedNode *_dummyHead;
};
/**
* 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);
*/
⚠️注意：
在deleteAtIndex接口中使用delete释放了tmp指针原本所指的那部分内存，但是被delete后的指针tmp的值并不是nullptr，而是随机值，即tmp成为了野指针，因此需要将tmp = nullptr。
206.反转链表
题目链接：https://leetcode.cn/problems/reverse-linked-list/
题目难度：简单
文章讲解：https://programmercarl.com/0206.翻转链表.html
视频讲解： https://www.bilibili.com/video/BV1nB4y1i7eL
题目状态：通过
个人思路：
构建一个新链表用于存储反转后的链表，再循环旧的链表，每循环到一个节点，就将该节点的值采用头插法插入到新链表中，最后返回新链表。
实现代码：
/**
* 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) {
if(head == nullptr) return head;
ListNode *newList = new ListNode();
ListNode *cur = head;
while(cur != nullptr) {
ListNode *tmp = new ListNode(cur->val);
tmp->next = newList->next;
newList->next = tmp;
cur = cur->next;
}
return newList->next;
}
};
过是过了，但看着那两个大大的new并且没有delete我就恶心，感觉自己又写了一坨……
其他思路：
1. 双指针法
a. 直接定义两个指针cur和pre，cur用于遍历，pre用于保存cur的前一个节点。
b. 每次遍历到下一个节点的时候，cur就会将它的下一个节点的指向指到自己的前一个节点pre，最后更新自己到原本的下一个节点。
代码：
/**
* 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) {
if(head == nullptr) return head;
ListNode *cur = head;
ListNode *pre = nullptr;
ListNode *tmp;
while(cur != nullptr) {
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
2. 递归法
思路和双指针法相同，代码如下：
/**
* 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) {
return reverse(nullptr, head);
}
ListNode *reverse(ListNode *pre, ListNode *cur) {
if(cur == nullptr) return pre;
ListNode *tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp);
}
};
还有种思路但是没看懂：
从后往前翻转指针指向
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
head->next = NULL;
return last;
}
};