1、链表定义

单链表

struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

通过上述自定义构造函数初始化节点：

ListNode* head = new ListNode(5); //这里指的是创建一个head节点，并将val(值)创建为5

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！这点要注意。

2、链表的操作

2.1 删除节点

删除D节点，如图所示：

只要将C节点的next指针指向E节点就可以了。然后要手动删除D节点 delete XXX;
需要注意的是，针对删除头节点时，还需要进行判断，比较好的做法是手动虚拟一个虚拟头节点，其值为空，其指针指向第一个节点位置.
其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

2.2 添加节点

如图所示：

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

2.3 性能分析

再把链表的特性和数组的特性进行一个对比，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

相信大家已经对链表足够的了解，后面我会讲解关于链表的高频面试题目，我们下期见！

力扣203：移除链表元素

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

解法1：先判断头指针是否符合删除条件

核心代码

while(head != nullptr && head->val == val){
     ListNode *temp = head;
     head = head->next;
     delete temp;
}

完整代码

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头节点
        while(head != nullptr && head->val == val){
            ListNode * tmp = head;
            head = head -> next;
            delete tmp;
        }
        //删除非头节点
       ListNode *cur = head;
        while(cur != nullptr && cur->next != nullptr){
            if(cur->next->val == val){
                ListNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }else{
                cur = cur->next;
            }
        }

        return head;

    }

};

这个需要注意的是，在阐述非头节点的时候，不要直接操作头节点，而是新建一个临时指针的方式来遍历，操作数据的基础上来避免修改head节点。

解法2：通过虚拟头节点的方式来处理

dumyHead
完整代码

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向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;
    }
};

思想就是虚拟一个头节点，然后通过这个虚拟节点不停的判断链表中的下一个节点是否是需要删除的节点。在执行的时候，为了避免操作空指针，需要进行判断head != nullptr && head->next != nullptr

解法3：通过递归的方式来处理

力扣707：设计链表

题目概述

你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。>
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

确实是一道很经典的题目，通过这个题目把链表相关的操作都讲解了。

题目解法

完整代码

class MyLinkedList {
public:


    //定义链表节点结构体
    struct LinkNode{
        int val;
        LinkNode *next;
        LinkNode(int val):val(val), next(nullptr){};
    };

    //初始化类
    MyLinkedList() {
        dummpHead = new LinkNode(0);//定义虚拟头节点
        size = 0;
    }

    //下面程序中如果难以理解，都可以假设链表中仅有1个节点来理解。
    //获取链表中下标为index的节点的值
    int get(int index) {
        //首先判断index的合法性，如果不合法则返回-1
        if(index < 0 || index > size - 1){
            return -1;
        }

        LinkNode *cur = dummpHead->next;
        while(index){
            cur = cur->next;
            index--;
        }
        return cur->val;    
    }

    //将一个值为val的节点插入头节点之前。
    void addAtHead(int val) {
        LinkNode *newHead = new LinkNode(val);
        newHead->next = dummpHead->next;
        dummpHead->next = newHead;
        size++;//不要忘记这步操作。
    }

    //将一个值为val的节点接入到链表最后一个节点后，插入的节点将成为最后一个节点。
    //重点是如何定位到最后一个节点。
    void addAtTail(int val) {
        LinkNode *newHead = new LinkNode(val);
        LinkNode *cur = dummpHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newHead;
        newHead->next = nullptr;
        size++;
    }

    //在指定节点前插入特定的节点
    void addAtIndex(int index, int val) {
        LinkNode *newHead = new LinkNode(val);
        if(index < 0) size = 0;
        if(index > size) return;
        LinkNode *cur = dummpHead;
        while(index--){
            cur = cur->next;
        }
        newHead->next = cur->next;
        cur->next= newHead;
        size++;
    }

    //删除下标为index的节点
    void deleteAtIndex(int index) {
        if(index < 0 || index >= size) return;
         LinkNode *cur = dummpHead;
        while(index--){
            cur = cur->next;
        }
        LinkNode *tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }

  

    //打印链表

    void printLinkedNodeList(){
        LinkNode *cur = dummpHead;
        while(cur->next != nullptr){
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

  private:
    int size;  //这里的size用来表示链表的大小，目前不包含自己定义的dummy节点
    LinkNode *dummpHead; //创建虚拟头节点，来实现整体操作的实现

};


/**
 * 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：反转链表

题目概述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

题目解法

双指针解法

思路：
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，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 *tmp;
        ListNode *cur = head;
        ListNode *pre = nullptr;
        while(cur){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return 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 *reverse(ListNode *pre, ListNode *cur){
        if(cur == nullptr) return pre;
        ListNode *tmp = cur->next;
        cur->next = pre;
        return reverse(cur, tmp);
    }
    
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
       }
};

递归解法真的很简洁。

遗留问题

Q1：关于空间复杂度和时间复杂度，还需要进行复习！

本节小结

书读百遍，其意自现，链表前期本来不明白，多看了几遍也就明白了。

1、链表定义

2、链表的操作

2.1 删除节点

2.2 添加节点

2.3 性能分析

力扣203：移除链表元素

解法1：先判断头指针是否符合删除条件

解法2：通过虚拟头节点的方式来处理

解法3：通过递归的方式来处理

力扣707：设计链表

题目概述

题目解法

力扣206：反转链表

题目概述

题目解法

双指针解法

递归解法

代码实现：

遗留问题

Q1：关于空间复杂度和时间复杂度，还需要进行复习！

本节小结

评论区(暂无评论)

我要评论

这里空空如也，快来评论吧~