203.移除链表元素
- 题目链接：[https://leetcode.cn/problems/remove-linked-list-elements/submissions/]
文章链接:[https://www.programmercarl.com/0203.移除链表元素.html#其他语言版本]
第一遍思路
先通过创建一个虚拟头结点，这样所有的节点情况相同。然后，对所有的节点进行相同的处理。
实现问题
对于链表题目很久没有做过，对于结构不熟悉。创建一个头结点写了好几遍都没写对。
正确的写法是使用构造函数直接构造一个指向head的头结点，在创建cur指针进行遍历。
点击查看代码
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
struct ListNode* dummyHead = new ListNode(0, head);
struct ListNode* cur = dummyHead;
if (head == nullptr)return nullptr;
while(cur->next!=nullptr){
if(cur->next->val == val){
ListNode* temp=cur->next;
cur->next=cur->next->next;
delete temp;
}
else{
cur=cur->next;
}
}
head=dummyHead->next;
delete dummyHead;
return head;
}
};
题后总结
- 思路没啥问题，但是对于c++不熟练，需要每天写题不断熟练。
- 要对删除掉的节点进行delete，防内存泄漏
- 链表可以用迭代写法，那么一定可以用递归写法，需要找时间练习一下递归写法。
707.设计链表
- 题目链接：[https://leetcode.cn/problems/design-linked-list/]
文章链接：[https://www.programmercarl.com/0707.设计链表.html#代码]
第一思路
对于初始化函数，我一直想不出怎么实现。我的理解是需实现要输入head=[1,2,3,4,5]初始化链表，然后找出头结点，才能开始后续，卡住了，一直想不明白。
链表的初始化只要创建一个虚拟头结点就可以，向之后添加节点完成整个链表是我们之后其他的函数需要完成的工作。
实现
点击查看代码
class MyLinkedList {
public:
struct Node{
int val;
Node* next;
Node() : val(0), next(nullptr){}
Node(int x) : val(x), next(nullptr){}
Node(int x, Node(*next)) : val(x), next(next){}
};
MyLinkedList() {
dummyHead = new Node(0);
_size=0;
}
int get(int index) {
if( index<0 || _size-1 < index){
return -1;
}
Node* cur=dummyHead->next;
while(index--){
cur=cur->next;
}
return cur->val;
}
void addAtHead(int val) {
Node* head=dummyHead->next;
Node* cur=new Node(val,head);
dummyHead->next=cur;
_size++;
}
void addAtTail(int val) {
Node* cur=dummyHead;
while(cur->next != nullptr){
cur=cur->next;
}
cur->next=new Node(val);
_size++;
}
void addAtIndex(int index, int val) {
if( index > _size) return;
else if(index<0)addAtHead(val);
else if(index == _size)addAtTail(val);
else{
Node* cur=dummyHead;
while(index--){
cur=cur->next;
}
Node* temp = new Node(val);
temp->next=cur->next;
cur->next=temp;
_size++;
}
}
void deleteAtIndex(int index) {
if(index >= _size || index < 0)return;
Node* cur = dummyHead;
while(index--)cur=cur->next;
Node* temp = cur->next;
cur->next=cur->next->next;
delete temp;
_size--;
}
void printLinkedList() {
Node* cur = dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
Node* dummyHead;
int _size;
};
/**
* 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);
*/
思路总结
这道题的容易出现错误的地方是要判断寻找的改节点还是节点的前一位。
206.反转链表
第一思路
- 首先固定住1号节点，作为first节点
- 进行循环，不断将后面的节点移动到头结点处
实现
点击查看代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr){return nullptr;}
ListNode* first = head;
while(first->next != nullptr){
ListNode* temp=first->next;
first->next=first->next->next;
temp->next=head;
head=temp;
}
return head;
}
};
文章做法
文中的做法是通过双指针不断改变链接的方向来进行，比我自己思考的方法容易理解一点
实现
点击查看代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
};
今日思考
今天花了大概4个多小时的时间来做题，比较久。主要问题在于设计链表画的时间比较多，链表的增删查都是固定的套路，需要将这种简单的套路熟练使用。
标签：Node,head,cur,val,随想录,next,链表,移除 From： https://www.cnblogs.com/suodi/p/16724044.html