算法训练营第三天 | 203.移除链表元素、707.设计链表 、206.反转链表

本文主要是介绍算法训练营第三天 | 203.移除链表元素、707.设计链表 、206.反转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关于链表我们应该了解什么：

---

问题（ 一 ）

题目描述 ：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

题目链接：

203. 移除链表元素 - 力扣（LeetCode）

---

问题分析：

          这到题目算是链表的基础操作 ， 我这里写的是链表的前面是一个虚拟头节点，这样我们就不用考虑删除元素是否是头节点这个情况了 。主要掌握虚拟头节点，当然可以不用这个方法，但是这样会时链表的操作变得更加简洁。  删除的核心操作就是，找到要删除节点的前一个节点：他的next 就是我们要删除的节点    如果删除的节点的前一个节点是p,   那么 p->next = p->next->next。

视频讲解：

手把手带你学会操作链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili

---

解决方案：

 ListNode* removeElements(ListNode* head, int val) {ListNode *virtualNode =new ListNode;    //定义一个虚拟头结点virtualNode->next=head;ListNode *temp=virtualNode;//遍历链表while( temp!= NULL && temp->next!=NULL){if(temp->next->val==val){   //找到了满足条件的节点//删除节点head=temp->next;temp->next=temp->next->next;delete head;continue;}temp=temp->next;}return virtualNode->next;}

问题（ 二  ）

题目描述 ：

设计链表，可以是单链表也可以是双链表。

题目链接：

707. 设计链表 - 力扣（LeetCode）

问题分析：

        我自己给出的答案是单链表的设计 ， 包括一些基础操作，增删查。我们需要知道的是链表也是从0开始计数的，删除和在指定位置插入，我们都是找到待操作位置的前一个位置。

视频讲解：

帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili

解决方案：

class MyLinkedList {    //才用虚拟头节点法public:MyLinkedList() {head = new ListHead;head->next = NULL;head->val = 0;size = 0;}//获取元素int get(int index) {//防御性编程if (!head ) return -1;    //链表不存在,或者为空if (head->next == NULL)  return -1;if (index < 0)   return -1;  //下标不合法  if (index >= size)  return -1;int i = 0;ListNode* p = head;  //指向虚拟头结点while (i <=index) {p = p->next;i++;}return p->val;}//头部添加void addAtHead(int val) {if (!head) return;ListNode* node = new ListNode;    //生成一个节点node->val = val;node->next = head->next;head->next = node;size++;}//尾部添加void addAtTail(int val) {if (!head) return;    //判断链表是否存在ListNode* node = new ListNode;    //生成一个节点node->val = val;ListNode* p = head;   //指向第一个节点while (p->next!=NULL) {p = p->next;}//循环结束后说明刚好处于最后一个位置node->next = p->next;p->next = node;size++;}//在指定位置添加void addAtIndex(int index, int val) {if (!head) return;   //链表不存在if (index < 0) return; //位置不合法if (index > size) return;ListNode* p = head;   //指向虚拟头结点while ( index--) {p = p->next;}ListNode* node = new ListNode;    //生成一个节点node->val = val;node->next = p->next;p->next = node;size++;}//删除位置的元素void deleteAtIndex(int index) {if (!head ) return;if (head->next == NULL)  return;   //没有元素if (index < 0)   return ;  //下标不合法  if (index >= size)  return ;LinkList* p = head;if (index == 0) {head->next = head->next->next;size--;return;}while ( index-- ) {p = p->next;}cout << p->val << endl;LinkList* temp = p->next;p->next = p->next->next;delete temp;size--;}void print() {ListNode* node = head->next;while (node) {cout << node->val << "  ";node = node->next;}cout << endl;}private://节点结构
typedef struct LinkList {struct LinkList* next;int val;
}ListHead,ListNode;ListHead* head;int size;   //链表的长度};

问题（  三  ） 

题目描述 ：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

题目链接：

206. 反转链表 - 力扣（LeetCode）

问题分析：

        这到题目，我们采用双指针的思路。指针 pro 用来记录我们head的前一个节点，开始没有翻转之前，head的前一个节点为NULL ，所有pro初始值为NULL，而我们的第二个指针 temp 则用来记录head的下一个节点。

 循环遍历我们的链表，终止条件是  head 指针为空，1-》2断开之后，1-》的next指向了 NULL，然后我们的  temp继续往后移动，而我们的 pro 则指向 head。

视频加文字讲解：

 解决方案：

ListNode* reverseList(ListNode* head) {if(!head)  return NULL;   //链表为空if(head->next==NULL) return head;    //只有一个元素的情况ListNode *pro=NULL ; //用来只想当前位置的前一个节点ListNode *temp=head ;while( head ){temp = temp->next;head->next=pro;pro=head;head=temp;}head=pro;return head;  
}

这篇关于算法训练营第三天 | 203.移除链表元素、707.设计链表 、206.反转链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---