当前位置： 首页 > article >正文

链表算法速成计划

article 2024/11/25 0:22:02

链表算法速成计划

1.准备工作

1.1创建链表节点结构体

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

1.2 在IDE中创建链表代码

ListNode* createRandomLinkedList(int length)
{
	if (length <= 0) return NULL;

	// 设置随机数种子

	std::random_device rd; // 随机数种子
	std::mt19937 gen(rd()); // Mersenne Twister 随机数引擎
	std::uniform_int_distribution<> dis(0, 99); // 随机数分布

	// 创建头节点，数据为0到99之间的随机值
	ListNode* head = NULL;

	// 循环创建其他节点
	for (int i = 1; i < length; ++i)
	{
		ListNode* newListNode = new ListNode(dis(gen) % 100);
		newListNode->next = head;
		head = newListNode;
	}


	return head;
}

1.3 打印链表和释放链表代码

// 打印链表的函数
void printLinkedList(ListNode* head)
{
	ListNode* current = head;
	while (current != NULL)
	{
		std::cout << current->val << " -> ";
		current = current->next;
	}
	std::cout << "NULL" << std::endl;
}

// 释放链表内存的函数
void freeLinkedList(ListNode* head)
{
	ListNode* current = head;
	while (current != NULL)
	{
		ListNode* nextListNode = current->next;
		delete current;
		current = nextListNode;
	}
}

1.4 示例代码

#include <iostream>
#include <random>

using namespace  std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* createRandomLinkedList(int length)
{
	if (length <= 0) return NULL;

	// 设置随机数种子

	std::random_device rd; // 随机数种子
	std::mt19937 gen(rd()); // Mersenne Twister 随机数引擎
	std::uniform_int_distribution<> dis(0, 99); // 随机数分布

	// 创建头节点，数据为0到99之间的随机值
	ListNode* head = NULL;

	// 循环创建其他节点
	for (int i = 1; i < length; ++i)
	{
		ListNode* newListNode = new ListNode(dis(gen) % 100);
		newListNode->next = head;
		head = newListNode;
	}


	return head;
}

// 打印链表的函数
void printLinkedList(ListNode* head)
{
	ListNode* current = head;
	while (current != NULL)
	{
		std::cout << current->val << " -> ";
		current = current->next;
	}
	std::cout << "NULL" << std::endl;
}

// 释放链表内存的函数
void freeLinkedList(ListNode* head)
{
	ListNode* current = head;
	while (current != NULL)
	{
		ListNode* nextListNode = current->next;
		delete current;
		current = nextListNode;
	}
}


int main() {

	// 创建链表
	for (int i = 1; i <= 5; i++)
	{
		ListNode* head = createRandomLinkedList(10);
		cout << "第" << i << "次样例:";
		printLinkedList(head);
		//本区域填写你的函数！！！！

		//ListNode* newhead = 你的函数(head);

		cout << "第" << i << "次结果:";
		printLinkedList(head);
		// 释放链表内存
		freeLinkedList(head);
	}
	return 0;
}

在这里插入图片描述

2. 基本操作（必须熟练默写！）

2.1 头插

ListNode* head_insert(ListNode* head, ListNode* node) //head为链表，ListNode为待插入节点
{
	//本代码正常head为NULL，也就是空链表
	node->next = head; //ListNode指向head
	head = node; //让ListNode作为新的头
	return head;
}

示例

int main() {
    ListNode* head = NULL;
    for (int i = 1; i <= 5; i++)
    {
        ListNode* newhead = new Node(i);
        head = head_insert(head, newhead);
        cout << "第" << i << "次插入结果:";
        printLinkedList(head);
    }

    return 0;
}

在这里插入图片描述

2.2 头删

ListNode* head_delete(ListNode* head) //head为链表
{
	if (head == NULL)return head; //为空就直接返回
	ListNode* cur = head; //记录待删除节点
	head = head->next; //头结点只想下一个
	free(cur); //释放cur结点
	return head;
}

示例

int main() {
    ListNode* head = NULL;
    for (int i = 1; i <= 5; i++)
    {
        Node* newhead = new Node(i);
        head = head_insert(head, newhead);
        cout << "第" << i << "次插入结果:";
        printLinkedList(head);
    }
    for (int i = 1; i <= 5; i++)
    {
        head = head_delete(head);
        cout << "第" << i << "次删除结果:";
        printLinkedList(head);
    }

    return 0;
}

在这里插入图片描述

2.3 中间节点插入（包括尾插）

ListNode* middle_insert(ListNode* head, int val, ListNode* node) //本代码理解意思即可，也就是说先查找到val值的节点，然后在其后面插入ListNode，尾插也可以用这个思想！
{
	ListNode* pre = head; //pre指插入位置的前一个节点也就是val值的节点
	while (pre)
	{
		if (pre->val != val) //如果没有找到val就继续找
			pre = pre->next;
		else //找到val后进行插入
		{
			node->next = pre->next;
			pre->next = node;
			break; //插入后退出循环
		}
	}
	return head; //返回链表头节点
}

示例

int main() {
    
    ListNode* head = NULL;
    for (int i = 1; i <= 5; i++)
    {
        ListNode* newhead = new ListNode(i);
        head = head_insert(head, newhead);
        cout << "第" << i << "次插入结果:";
        printLinkedList(head);
    }

    //在1后面插入10
	ListNode* newhead = new Node(10);
    middle_insert(head, 1, newhead);
    cout << "插入结果:";
    printLinkedList(head);

    //在5后面插入20
	newhead = new Node(20);
    middle_insert(head, 5, newhead);
    cout << "插入结果:";
    printLinkedList(head);
    return 0;
}

在这里插入图片描述

2.4 删除中间节点（包括尾删）

ListNode* middle_delete(ListNode* head, int val) //先查找到val对应的节点，然后删除该节点
{
	ListNode* pre = NULL; //pre是需要删除节点的前一个位置，注意：在删除节点中前一个位置很重要，因为你只有通过前一个结点才能将链表连接起来！
	if (head->val != val) //如果需要删除的是第一个节点，那么他没有前一个节点，所以你得判断一下，如果删除的不是第一个节点，那么就可以将head赋值给pre，然后进行查找
	{
		pre = head;
	}
	else //如果要删除的是第一个节点也就是头删！
	{
		head = head_delete(head);
		return head;
	}
	while (pre->next) //pre->next就是我们要查找的待删除节点，所以这个一定不是NULL的，故while条件是这个
	{
		if (pre->next->val != val) //如果不等就往下一个查找
		{
			pre = pre->next;
		}
		else //如果查到
		{
			ListNode* cur = pre->next; //记录待删除节点
			pre->next = cur->next; //连接前后节点
			free(cur);
			break;
		}
	}
	return head;
}

示例

int main() {
    
    ListNode* head = NULL;
    for (int i = 1; i <= 5; i++)
    {
        ListNode* newhead = new ListNode(i);
        head = head_insert(head, newhead);
        cout << "第" << i << "次插入结果:";
        printLinkedList(head);
    }
    head = middle_delete(head,4);
    cout << "删除4后结果:";
    printLinkedList(head);

    head = middle_delete(head, 5);
    cout << "删除5后（也就是删除第一个位置）结果:";
    printLinkedList(head);

    head = middle_delete(head, 1);
    cout << "删除1后（也就是删除最后个位置）结果:";
    printLinkedList(head);
    return 0;
}

在这里插入图片描述

3. 力扣代码练习

3.1 合并两个有序链表

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newhead=new ListNode(-1);//创建哨兵头节点
        ListNode* tail=newhead;//永远指向新链表的尾部的节点
        while(list1&&list2)
        {
            if(list1->val<list2->val)//如果list1头节点小就让list1头节点尾插到newhead
            {
                ListNode* cur=list1;//cur是指向该头节点
                list1=list1->next;//然后list1就指向他的下一个节点，也就是丢弃了之前的头节点
                tail->next=cur;//newhead尾节点指向cur节点
                tail=tail->next;//tail更新到下一个节点
            }else
            {//同上
                ListNode* cur=list2;
                list2=list2->next;
                tail->next=cur;
                tail=tail->next;
            }
        }
        if(list1!=nullptr)//到这一步就是会出现要么list1还剩余节点，list2没有，要么list2还剩余节点，list1没有，这个时候只需要将整条链接到newhead尾巴后面
        {
            tail->next=list1;
        }
        if(list2!=nullptr)
        {
            tail->next=list2;
        }
        return newhead->next;//返回头节点（要范围next，应为newhead是哨兵）
    }
};

3.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) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* pre=head;//pre指向要删除节点的前一个位置，也就是说pre是指第一个出现该数字的节点，之前后的相同节点都要被删除
        while(pre&&pre->next)//这里也要保证pre->next不是空，因为可能pre是最后一个节点，那么就没有意义了，也就是说这个循环条件是运行到倒数第二个节点
        {
            if(pre->val==pre->next->val)//如果相等这删除这个节点，然后继续循环
            {
                //ListNode* cur=pre->next;
                pre->next=pre->next->next;
                //free(cur);//考试的时候需要这样写，也就是要释放结点，但是OJ不给你释放所以我就屏蔽掉这两行代码！
    
            }
            else//如果不相等就pre指向下一个节点，  如果不懂自己根据样例画图看看
            {
                pre=pre->next;
            }
        }
        return head;
    }
};

3.3 环形链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //本题需要特殊技巧：快慢指针
        ListNode*fast=head;
        ListNode*slow=head;
        while(fast&&fast->next)//这里的判断条件是防止fast走到NULL，出现空指针异常  因为fast每次要走两步，所以要保证fast可以走到第二步，也就是说fast和fast->next都不能为空
        {
            fast=fast->next->next;//fast走两步
            slow=slow->next;//slow走一步
            if(fast==slow)return true;//如果是循环链表，那么fast一定会追上slow，然后就返回true
        }
        return false;//走到这一步是因为head不是循环链表，fast走到尾巴了，故跳出循环
    }
};

3.4 移除链表元素

/**
 * 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) {
        ListNode* newhead=new ListNode(-1);//创建一个哨兵，处理特殊情况（删除第一个也就是头删要特殊处理比较麻烦）
        newhead->next=head;
        ListNode* pre=newhead;//需要删除节点的前一个
        while(pre&&pre->next)//pre->next是可能需要删除的结点，故他一定要存在
        {
            if(pre->next->val==val)//如果pre->next和val相同则要删除该节点
            {
                pre->next=pre->next->next;
            }
            else//否则pre往下遍历
            {
                pre=pre->next;
            }
        }
        return newhead->next;
    }
};

3.5 反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //头插的应用
        ListNode* newhead=NULL;
        while(head)
        {
            ListNode* cur=head;//记录需要头插的结点
            head=head->next;//head往下遍历
            cur->next=newhead;//cur指向头插链表的头
            newhead=cur;//cur作为 新 头插链表的头节点
        }
        return newhead;
    }
};

3.6 链表的中间结点

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast&&fast->next)//查找链表中间节点，快指针走到结束，慢指针正好到中间
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
};

3.7 回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {//算法思路：找到中间节点，将后面一半反转，然后对比
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        //这个时候slow应该是中间节点
        //但是这个时候有两个情况
        //1. A->B->C  链表长度为奇数时 fast不为空，slow是中间那个节点
        //2. A->B->C->D 链表偶数时,fast为空，slow是中间元素上取整，也就是C
        //所以这里要分情况

        if(fast)
        {
            slow=slow->next;//这里对应第一种情况，让slow到下一个节点，这样就可以让两种情况的判断过程一样
        }

        //反转链表:模板，本质就是头插 理解背上
        ListNode* newhead=NULL;
        while(slow)
        {
            ListNode* cur=slow;
            slow=slow->next;
            cur->next=newhead;//头插
            newhead=next;
        }
        while(newhead)//这样就得到两个链表，head和newhead，但是这里newhead肯定是后面半部分，所以我们使用newhead为空来判断是否结束，每次都判断对应节点是否相等，不相等就不是回文串，相等就都往下一个遍历，直到遍历结束那就是回文串
        {
            if(newhead->val!=head->val)
            {
                return false;
            }
            newhead=newhead->next;
            head=head->next;
        }
        return true;
        
    }
};

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

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //算法思想：让cur先走n个节点，然后让pre从头开始和cur一起走，cur走到结束了，那么pre就走到要删除节点的前一个（题目翻译就是说让pre少走n个节点）

        // 分析样例：1->2->3->4->5->NULL n=2，也就是说我们要删除4，那么我们要找到3这个位置（也就是5-2=3这个位置，那么我们只需要走两次就可以走到3），我们让cur先走2次，然后让pre和cur一起走，一直让cur走到最后一个节点的时候，pre就是要删除节点的前一个位置
        ListNode* cur=head;
        for(int i=0;i<n;i++)
        {
            if(cur==NULL)//这个是用来判断n是否合理的，比如说我长度一个是4个，你n给我5那我在遍历head的时候就会出现cur走到结束了，这个时候就什么不要操作直接返回head
                return head;
            cur=cur->next;
        }

        if(cur==NULL) return head->next;//这里如果cur走到了尾巴，那么就相当于头插，我们只需要返回头的下一个节点，还是以：1->2->3->4->5->NULL n=5为例，这个时候cur从头5个节点那么就会跑到尾巴，那么这个时候相当于头删
        //删除算法中头删和中间删除（尾删）要分别处理，我给你的代码模板中也说了
        ListNode* pre=head;
        while(cur->next)//cur走到后一个节点
        {
            cur=cur->next;
            pre=pre->next;
        }
        pre->next=pre->next->next;//删除中间的结点方法
        return head;

    }
};

3.9 排序链表（本题OJ需要nlogn，但是我们考试写出n^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) {}
 * };
 */
class Solution {
public:

    ListNode* sortList(ListNode* head) {
        //对链表进行排序，使用插入排序思想
        ListNode* newhead=NULL;//排序后的头结点
        while(head)
        {
            ListNode* cur=head;//将要插入到新链表的结点
            head=head->next;//原来链表头结点到下一个
            if(newhead==NULL||cur->val<newhead->val)//如果一开始为空，或者cur比第一个新链表头结点小，那么只能头插
            {
                cur->next=newhead;
                newhead=cur;
            }
            else
            {
                ListNode *pre=newhead;//指向将要插入位置的前一个节点
                while(pre)
                {
                    if(pre->next==NULL||cur->val<pre->next->val)//pre->next==null是查找到尾巴了，只能插入到最后一个位置，cur->val<pre->next->val是cur比pre->next节点值小，所以就要插入到pre结点后面
                    // 比如插入1   插入到-1->0->1->2->3  那么根据插入排序思想就是要插入到第一个比自己大的结点前面
                    {
                        cur->next=pre->next;
                        pre->next=cur;
                        break;//插入成功就跳出循环
                    }
                    pre=pre->next;//否则pre就一直往后查找
                }
            }
        }
        return newhead;//返回新链表头结点
    }
};

http://www.kler.cn/a/407875.html

相关文章：

  • linux基本命令（1）
  • Android Gradle 插件和 Android Studio 兼容性
  • 从 Mac 远程控制 Windows：一站式配置与实践指南20241123
  • 基础知识学习上
  • AI智能稿件排版系统订单管理系统
  • Diving into the STM32 HAL-----DAC笔记
  • 探索C++中的map和set容器
  • 【jvm】从字节码角度看待对象创建流程
  • Claude Opus MetaPrompt 系统详解
  • 论文阅读 SimpleNet: A Simple Network for Image Anomaly Detection and Localization
  • 【C++】踏上C++学习之旅（十）：深入“类和对象“世界，掌握编程黄金法则（五）（最终篇，内含初始化列表、静态成员、友元以及内部类等等）
  • Spring 中的 ProxyFactory 创建代理对象
  • i春秋-123(文件上传绕过，双写绕过)
  • Vue + Websocket播放PCM（base64转ArrayBuffer、 字符串转ArrayBuffer）
  • RabbitMQ 篇-深入了解延迟消息、MQ 可靠性（生产者可靠性、MQ 可靠性、消费者可靠性）
  • GitLab使用示例
  • 储能场站安全风险挑战
  • OceanBase数据库产品与工具介绍
  • 深入探讨 Puppeteer 如何使用 X 和 Y 坐标实现鼠标移动
  • 彻底理解如何保证Redis和数据库数据一致性问题
  • K8s 一键部署 MongoDB 的 Replica-Set 和 MongoDB-Express
  • 《AI大模型开发笔记》Faster-Whisper 免费开源的高性能语音识别模型
  • 国外云计算服务器租用攻略
  • QDUOJ（青岛大学在线评测系统）
  • 力扣 238. 除自身以外数组的乘积
  • muduo库的使用