【代码随想录】算法训练营 第三天 第二章 链表 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->next
            cur->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);
    }
 
};