【代码随想录】算法训练营 第三天 第二章 链表 Part 1

目录

链表基础

 链表的定义

203. 移除链表元素

题目

思路

代码

直接删除法

虚拟头结点辅助法

707. 设计链表

题目

思路

代码

206. 反转链表

题目

思路

代码

双指针法

递归法

---

链表基础

链表是一种通过指针串在一起的线性结构，每个节点都由数据域和指针域组成，数据域存放节点数据，指针域存放指向下一个节点的指针，最后一个节点的指针指向null，也即这个指针为空指针。

 链表的定义

随想录中，标准的单链表定义如下：

struct ListNode {int val; // 数据域里的数据 ListNode *next; // 指针域里指向下个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 构造函数，直接定义并初始化一个节点的数据域值为x 
};ListNode* head = new ListNode(5); // 通过自己定义的构造函数来初始化节点，直接赋值为5 ListNode* head = new ListNode(); 
head->val = 5; // 使用默认的构造函数来初始化节点，但是这里需要自己赋值 

203. 移除链表元素

题目

思路

力扣里已经定义好了链表，所以我们只需要使用ListNode* 来定义指针即可。

这道题需要我们删除和目标值相同的节点，所以我们的思路简单粗暴，一个一个比下去然后遇到就删除就是了，但是这里有一个问题，就是我们要如何删除一个节点呢，其实很简单，要删除一个节点分三步，第一步，定义一个指针指向该节点，第二步，将原本指向该节点的指针指向这个节点的下一个节点，第三步，删除我们新定义的这个指针（同时把指针指向的节点也删了）。

我们的代码有两种做法，一种是直接开干，将要删的节点分为头结点和中间节点，头结点先删，中间节点再用一个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) {while (head != NULL && head->val == val) {ListNode* tmp = head;head = head->next;delete tmp;}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;}
};

虚拟头结点辅助法

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* cur = dummy;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 = dummy->next;return head;}
};

707. 设计链表

题目

设计一个链表，实现以下功能：

• 获取元素；
• 表头添加元素；
• 表尾添加元素；
• 表中添加元素；
• 删除元素。

思路

这就是最简单的手搓链表了（bushi），在这里我们可以像上面那样给链表的前面添加一个虚拟头结点dummy，这样就不用考虑对头结点的特殊情况了，所有节点都一视同仁。

这就没什么思路不思路的了，思想很简单，实现是关键，真正写出来并且一点错没有，那就可以了，具体实现就看下面的代码吧。

注意，当你要开始复习链表的时候，就照着这个代码多抄多背，以后面试再也不用担心！

代码

class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val) : val(val), next(nullptr){}};// 初始化链表MyLinkedList() {dummy = new LinkedNode(0); // 定义一个虚拟头结点size = 0; // 链表的初始长度为0}// 获取第index个节点数值，如果index非法则直接返回-1，index从0开始int get(int index) {if (index < 0 || index > size - 1) {return -1;}LinkedNode* cur = dummy->next;while (index--) { // index可以看作数组下标，cur是从下标为0的节点开始的，所以这里循环index次没错cur = cur->next;}return cur->val;}// 在链表前面插入一个节点，插入完后新的节点称为链表的新头结点void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = dummy->next;dummy->next = newNode;size++;}// 在链表最后添加一个节点void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = dummy;while (cur->next != nullptr) {cur = cur->next;}cur->next = newNode;size++;}// 在链表中第index个节点前插入新节点void addAtIndex(int index, int val) {if (index > size) return;if (index < 0) index = 0;LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = dummy;while (index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;size++;}// 删除第index个节点void deleteAtIndex(int index) {if (index > size - 1 || index < 0) {return;}LinkedNode* cur = dummy;while (index--) {cur = cur->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = nullptr;size--;}// 打印链表void print() {LinkedNode* cur = dummy;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}
private:int size;LinkedNode* dummy;
};

206. 反转链表

题目

思路

反转链表，就是从一个链表的第一个有效节点开始，逐一移出原链表，放到新链表的开头，

这样虽然原链表是从前往后拿走节点，但是新链表是从后往前一个一个加进去，这就完成了反转。

代码

双指针法

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur = head; // 指向头结点ListNode* pre = NULL; // 新链表的头指针while (cur) { // 当原链表中还存在节点时temp = cur->next; // 保存cur的下一个节点，因为接下来要改变cur->nextcur->next = pre; // 此时cur这个节点的下一个是新链表的第一个节点pre = cur; // 然后pre指针指向现在cur的这个结点cur = temp; // cur指向原链表的下一个结点}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);}};