学习新知识链表,刷题3道,先学习链表理论基础,然后刷题。 203.移除链表元素 707.设计链表 206.反转链表
● 203.移除链表元素
题目链接/文章讲解/视频讲解::https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
碎碎念:思路都会,代码语法不知道怎么写,伪代码写的太多也不好,还是得上机啊,两个版本,第一个是不加虚拟头结点,第二个是加的,实践证明加了的好用。
ps:得补c++语法了,要学的可真多啊,我还在输液,心情很不美丽。
1.直接使用原来的链表来进行移除节点操作:
class Solution { public: ListNode* removeElements(ListNode* head, int val) { //删除头节点 while(head != NULL && head -> val == val){ ListNode* tmp = head; //链表创建新指针 head = head -> next; delete tmp; //释放空间,c语言是free() } //删除非头结点。 ListNode* cur = head; while(cur != NULL && cur -> next != NULL){ if(cur -> next ->val == val){ ListNode* tmp = cur -> next; cur -> next = cur -> next -> next; delete tmp; } else{ cur = cur -> next; } } return head; } }; 2.设置一个虚拟头结点在进行移除节点操作: class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); //设置新结点的写法 dummyHead -> next = head; ListNode* cur = dummyHead; while(cur -> next != NULL){ if(cur -> next -> val == val){ ListNode* tmp = cur -> next; cur -> next =cur -> next -> next; delete tmp; } else{ cur = cur -> next; } } head = dummyHead -> next; delete dummyHead; return head; } };● 707.设计链表
题目链接/文章讲解/视频讲解:https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
碎碎念:链表的常用操作,需要掌握。
class MyLinkedList { public: struct LinkedNode{ //构建链表结点的结构体 int val; LinkedNode* next; LinkedNode(int val):val(val),next(nullptr){} }; //初始化链表 MyLinkedList() { dummyhead = new LinkedNode(0); //定义虚拟头结点,不是真的结点 size = 0; } //获取链表中第 index 个节点的值。如果索引无效,则返回-1。 int get(int index) { if(index > (size - 1) || index < 0){ return -1; } LinkedNode* cur = dummyhead -> next; while(index--){ cur = cur -> next; } return cur -> val; } //在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。 void addAtHead(int val) { LinkedNode* newNode = new LinkedNode(val); //创建新结点,并赋值为val newNode -> next = dummyhead -> next; dummyhead -> next = newNode; size++; } //将值为 val 的节点追加到链表的最后一个元素。 void addAtTail(int val) { LinkedNode* newNode = new LinkedNode(val); LinkedNode* cur = dummyhead; while(cur -> next != nullptr){ //nullptr是C++空指针类型的关键字 cur = cur -> next; } cur -> next = newNode; size++; } //在链表中的第 index 个节点之前添加值为 val 的节点。 //如果 index 等于链表的长度,则该节点将附加到链表的末尾。 //如果 index 大于链表长度,则不会插入节点。 //如果index小于0,则在头部插入节点。 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++; } //如果索引 index 有效,则删除链表中的第 index 个节点。 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; };
● 206.反转链表
题目链接/文章讲解/视频讲解:https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
碎碎念:先是双链表指针法,然后根据它的思想可以改写成面试官偏爱的递归写法,emmmm,感觉遍历一遍,挨个头插也是可以的,回头试一下。
PS:休息了,不对,去打游戏了,好像有一点点心动的感觉,喜欢一个人就是要和她一起打很多很多把游戏,散会!
双链表指针法:
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;
}
};
递归法:
class Solution { public: ListNode* reverse(ListNode* pre,ListNode* cur){ if(cur == NULL) return pre; ListNode* temp = cur->next; cur->next = pre; // 可以和双指针法的代码进行对比,如下递归的写法,其实就是做了这两步 // pre = cur; // cur = temp; return reverse(cur,temp); } ListNode* reverseList(ListNode* head) { // 和双指针法初始化是一样的逻辑 // ListNode* cur = head; // ListNode* pre = NULL; 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
head->next = NULL;
return last;
}
};
标签:head,ListNode,cur,val,训练营,随想录,next,链表,算法 From: https://www.cnblogs.com/zzw0612/p/17015133.html