门户网站源码入驻,WordPress点击logo返回首页,做360手机网站优化,深圳百度关键词● 自己看到题目的第一想法
203.移除链表元素
方法一#xff1a;
思路#xff1a; 设置虚拟头节点 dummyhead 设置临时指针 cur 遍历 整个链表 循环#xff1a; 如果 cur !nullptr cur-next !nullptr 则 遍历链表 否则结束遍历 如果 cur-next val 则…● 自己看到题目的第一想法
203.移除链表元素
方法一
思路 设置虚拟头节点 dummyhead 设置临时指针 cur 遍历 整个链表 循环 如果 cur !nullptr cur-next !nullptr 则 遍历链表 否则结束遍历 如果 cur-next val 则 cur-next cur-next-next 如果 cur-next !val 则 cur cur-next
返回 return dummyhead-next
注意用while循环代码
/*** 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) {ListNode* dummyhead new ListNode(0);dummyhead-next head;ListNode* cur dummyhead;while(cur !nullptr cur-next !nullptr){if(cur-next-val val){cur-next cur-next-next;}else{cur cur-next;}}head dummyhead-next;delete dummyhead;return head;}
};运行结果
方法二 思路 直接在原链表上操作 1.头节点是val值 删除头节点 head head-next; 2.头节点不是val值 定义一个临时变量cur 遍历整个链表 循环 : 如果cur !nullptr cur-next !nullptr 则 遍历链表 否则结束遍历 如果 cur-next val 则 cur-next cur-next-next 如果 cur-next !val 则 cur cur-next
返回 return head; 注意 代码
/*** 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 *cur head;while(cur !nullptr cur-next !nullptr){if(cur-next-val val ){cur-next cur-next-next;}else{cur cur-next;}}return head;}
};运行结果 707.设计链表
思路注意: cur应该指向_dummyhead 还是_dummyhead-next; 链表的构造struct 还有 private中 链表的 定义代码
class MyLinkedList {
public:
struct ListNode{int val;ListNode* next ;ListNode(int val): val(val), next(nullptr){}
};MyLinkedList() {_size 0;_dummyhead new ListNode(0);}int get(int index) {if(index(_size-1) || index0){return -1;}ListNode* cur _dummyhead;while(index){cur cur-next;index--;}return cur-next-val;}void addAtHead(int val) {ListNode* newnode new ListNode(val);newnode-next _dummyhead-next;_dummyhead-next newnode;_size;}void addAtTail(int val) {ListNode* cur _dummyhead;ListNode* newnode new ListNode(val);while(cur !nullptr cur-next !nullptr){cur cur-next;}cur-next newnode;_size;}void addAtIndex(int index, int val) {ListNode* newnode new ListNode(val);if(index0) index 0;if(index _size) return ;ListNode * cur _dummyhead;while(index--){cur cur-next;}newnode-next cur-next;cur-next newnode;_size;}void deleteAtIndex(int index) {if(index0 || index(_size-1)){return ;}ListNode*cur _dummyhead;while(index--){cur cur-next;}cur-next cur-next-next;_size--;}private:int _size;ListNode* _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);*/
运行结果
206.反转链表
方法一 思路双指针 定义pre null, cur head, 临时变量temp保存 cur-next; 循环 cur ! null让cur-next pre; pre cur; cur temp;返回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) {ListNode* cur head;ListNode* pre nullptr;ListNode* tmp ;while(cur !nullptr){tmp cur-next;cur-next pre ;pre cur;cur tmp;}return pre;}
};运行结果 方法二 思路递归法 先完成翻转的第一步: 确定终止条件 curnull 返回 pre 循环体 cur -next pre 递归下去 return reverse(cur, tmp) 注意 代码
/*** 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* reverse(ListNode* pre, ListNode* cur ){if(cur nullptr) return pre;ListNode* temp;temp cur-next;cur-next pre;return reverse(cur, temp);}ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}
};运行结果
