系列综述：
💞目的：本系列是个人整理为了秋招算法的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于代码随想录进行的，每个算法代码参考leetcode高赞回答和其他平台热门博客，其中也可能含有一些的个人思考。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈数据结构基础知识总结篇

---

---

😊点此到文末惊喜↩︎

---

一、链表理论基础

链表的定义

1. 单链表数据结构
   • 链表由值和下一个节点指针组成
   • 成员初始化构造函数，如果不定义，C++也会进行默认生成

   struct listNode{
   	int val;
   	listNode *next;
   	listNode(int x):val(x), next(NULL){}
   }
   

---

移除链表元素

1. 链表基本操作
   • 添加虚拟头节点vHead，统一遍历操作。
   • 删除链表中的节点，不要忘记delete释放
2. 题目
   

   	/**
    * 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) {}
    * };
    */
   ListNode* removeElements(ListNode* head, int val) {
       // 定义虚拟头节点
       ListNode *vHead = new ListNode(0, head);
       ListNode* cur = vHead;// 定义工作指针cur
       while(cur->next != nullptr){
           if(cur->next->val == val){// 为了获取操作节点的前一个节点进行删除
               ListNode* tmp = cur->next;
               cur->next = cur->next->next;
               delete tmp;
           }else{
               cur = cur->next;// 工作指针++
           }
       }
       // 删除头节点
       head = vHead->next;
       delete(vHead);
       return head;
   }
   

实现链表相关函数

1. 相关题目

实现 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() {
        vHead = new LinkNode(0);
        size = 0;
    }
    // 根据索引值获取对应节点值
    int get(int index) {
        if(index < 0 || index > (size-1)) 
            return -1;
        // *****带头节点的索引值定位********
        LinkNode* cur = vHead->next;
        while(index--){
            cur = cur->next;
        }
        // ************************************
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkNode* node = new LinkNode(val);
        node->next = vHead->next;
        vHead->next = node;
        ++size;
    }
    
    void addAtTail(int val) {
        LinkNode* node = new LinkNode(val);
        LinkNode *cur = vHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = node;
        ++size;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size) return;
        if(index < 0) index = 0;
        LinkNode* node = new LinkNode(val);
        LinkNode* cur = vHead;
         while(index--){
            cur = cur->next;
        }
        node->next = cur->next;
        cur->next = node;
        size++;

    }
    
    void deleteAtIndex(int index) {
        if(index < 0|| index >= size) 
            return ;
        LinkNode *cur = vHead;
        while(index--){
            cur = cur->next;
        }
        LinkNode *tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;


    }

    private:
        LinkNode *vHead;// 首地址
        int size;// 大小
};

---

二、双指针

反转链表

1. 头插法可以进行链表的反转
   • 尽量使用明确的逻辑关系，减少变量的转换
   • 先进行状态变量的状态保存，后进行逻辑处理

   ListNode* reverseList(ListNode* head) {
           if(head == nullptr)
                   return nullptr;
           // 头插法
           ListNode* vHead = new ListNode(0); // 虚拟头节点
           // 被遍历链表的工作指针
           ListNode* cur = head;
           ListNode* hind;
          // 开始遍历
           while(cur!= nullptr){
               hind = cur->next;// 一定要确切的使用逻辑关系
               // 头插法
               cur->next = vHead->next;
               vHead->next = cur;
               cur = hind;   
           }
           return vHead->next;
       }
   

---

交换相邻链表节点

1. letcode题目网址
   

   ListNode* swapPairs(ListNode* head){
   	// 健壮性检查
   	if(head == nullptr)
   	    return nullptr;
   	
   	// 指向操作节点组的第一个和第二个
   	ListNode* prior_first;
   	ListNode* prior_second;-
   	// 增加虚拟头节点
   	ListNode* vHead = new ListNode(0);
   	vHead->next = head;
   	ListNode *cur = vHead;
   	while(cur->next != nullptr && cur->next->next != nullptr){
   	    prior_first = cur->next;
   	    prior_second = cur->next->next;
   	    prior_first->next = prior_second->next;
   	    prior_second->next = prior_first;
   	    cur->next = prior_second; 
   	    cur = prior_second->next;// cur指向被操作节点组的前一个
   	}
   	return vHead->next;
   }
   

---

删除链表的倒数第 N 个结点

1. letcode题目
   

   ListNode* removeNthFromEnd(ListNode* head, int n) {
   	if(n < 0 || head == nullptr)
   	    return nullptr;
   	// 快慢指针拉开n个节点的距离
   	ListNode *vHead = new ListNode(0);
   	vHead->next = head;
   	ListNode *slow = vHead;
   	ListNode *fast = vHead;
   	// 让slow指向被删除节点的前一个
   	while(n--){
   	    fast = fast->next;
   	}
   	// 同步移动
   	while(fast->next != nullptr){
   	    fast = fast->next;
   	    slow = slow->next;
   	}
   	// 删除节点
   	slow->next = slow->next->next;
   	
   	return vHead->next;
   }
   

---

链表相交

1. letcode题目链接
   

   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
       ListNode *curA = headA;
       ListNode *curB = headB;
       
       int lenA = 0;
       int lenB = 0;
       // 计算A和B的长度
       while(curA != nullptr){
           lenA++;
           curA = curA->next;
       }
       while(curB != nullptr){
           lenB++;
           curB = curB->next;
       }
       curA = headA;
       curB = headB;
       // 求两链的差距
       int dis = 0;
       if(lenA > lenB){
           dis = lenA-lenB;
           while(dis--){
               curA = curA->next;
           }
       }else{
           dis = lenB-lenA;
           while(dis--){
               curB = curB->next;
           }
       }
   
       // 同步移动判断指针
       while(curA != curB){
           if(curA == nullptr || curB == nullptr){
               return nullptr;
           }
           curA = curA->next;
           curB = curB->next;
       }
   
       return curA;
   }
   

2. 有点东西的写法

   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
           ListNode *A = headA, *B = headB;
           // 核心在于交换头节点
           while (A != B) {
               A = A != nullptr ? A->next : headB;
               B = B != nullptr ? B->next : headA;
           }
           return A;
       }
   

---

链表相交

1. letcode题目链接
   • 一个节点的next是否能访问，需要判断该节点是否存在
   • 只写容易判断的逻辑，其他的交给else

   ListNode *detectCycle(ListNode *head) {
       ListNode* slow=head;
       ListNode* fast=head;
       while(fast!=NULL&&fast->next!=NULL){
           slow=slow->next;
           fast=fast->next->next;
           if(slow==fast){
               slow=head;
               while(slow!=fast){
                   slow=slow->next;
                   fast=fast->next;
               }
               return fast;
           }
       }
       return NULL;
    }
   

---

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。 不如点赞·收藏·关注一波

---

🚩点此跳转到首行↩︎

参考博客

1. 代码随想录
2. letcode