「代码随想录算法训练营」第三天 | 链表 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;
}
};