【基础算法】链表相关题目

系列综述：

💞目的：本系列是个人整理为了
秋招算法
的，整理期间苛求每个知识点，平衡理解简易度与深入程度。

🥰来源：材料主要源于
代码随想录
进行的，每个算法代码参考leetcode高赞回答和其他平台热门博客，其中也可能含有一些的个人思考。

🤭结语：如果有帮到你的地方，就

点个赞

和

关注一下

呗，谢谢🎈🎄🌷！！！

🌈

数据结构基础知识总结篇

文章目录

😊

点此到文末惊喜↩︎

一、链表理论基础

链表的定义

单链表数据结构
- 链表由
  值
  和
  下一个节点指针
  组成
- 成员初始化构造函数
  ，如果不定义，C++也会进行默认生成
```
struct listNode{
	int val;
	listNode *next;
	listNode(int x):val(x), next(NULL){}
}
```

移除链表元素

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

题目

	/**
 * 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;
}

实现链表相关函数

相关题目

实现 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;// 大小
};

二、双指针

基本快慢指针

// 初始化快慢指针
int slow = 0;
int fast = 0;
// 快指针未超边界
while(fast < nums.size()){
	if(nums[slow] == val){
		doing();
		++slow;
	}	
	++fast;
}

反转链表

头插法可以进行链表的反转

尽量使用明确的逻辑关系，减少变量的转换
先进行状态变量的状态保存，后进行逻辑处理

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;
    }

交换相邻链表节点

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 个结点

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;
}

链表相交

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;
}

有点东西的写法

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;
    }

链表相交

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;
 }

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。

不如点赞·收藏·关注一波

🚩

点此跳转到首行↩︎

参考博客

原文链接：https://blog.csdn.net/qq_43840665/article/details/129716687

文章目录

一、链表理论基础

链表的定义

移除链表元素

实现链表相关函数

二、双指针

反转链表

交换相邻链表节点

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

链表相交

链表相交

参考博客

你可能也喜欢