数据结构:链表(经典算法例题)详解

news/2024/12/22 20:47:37 标签: 数据结构, 链表

目录

1.移除链表元素

2.反转链表

3.链表的中间结点

4.合并两个有序链表

5.环形链表的约瑟夫问题

6.分割链表


我以过客之名,祝你前程似锦

1.移除链表元素

(1)题目:

https://leetcode.cn/problems/remove-linked-list-elements/description/

(题目来源)

(2)解析:
这题的具体实现有两种思路

思路一:遍历链表,释放值为val的结点 

思路二:找值不为val的结点并将其尾插到新链表

这题我为什么采用思路二而不采用思路一关键就是思路一虽然看上去简单粗暴,但它在实现过程中涉及了删除链表中元素的操作,这意味着对链表之间结点指向的修改更为麻烦而且伴随着容易遗忘释放内存而产生内存泄漏的风险,所有这里较优解还是思路二,无论是思路清晰度和实现操作的复杂度都比思路一要好些,以下就是思路二的具体实现代码:

#include<stdio.h>


  typedef struct ListNode 
  {
      int val;
      struct ListNode *next;
  }ListNode;
 
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    //创建一个空链表
    ListNode* newHead;
    ListNode* newTail;
    newHead = newTail = NULL;

    //遍历原链表
    ListNode* pcur = head;
    while (pcur)
    {
        //找值不为val的结点,尾插入新链表
        if (pcur->val != val)
        {
            //链表为空
            if (newHead == NULL)
            {
                newHead = newTail = NULL;
            }
            //链表不为空
            else
            {
                newTail->next = pcur;
                newTail = newTail->next;//尾插:先将原尾结点的next指针改方向再改新尾结点(newTail这个结构体类型的指针的指向)
            }
        }
        pcur = pcur->next;
    }

//这里有两点值得注意,一就是如果程序仅仅运行到这里是不可以的,如果原链表最后一个数据也是val,代码到此为止是会在新链表最后插入这个val代表的结点的,具体原因我会在正文解释
    if (newTail)
   {
       newTail->next = NULL;
   }
       return newHead;
}

但在思路二插入链表的过程中有两点特别值得关注:

        一就是我在倒数第二行代码里所展示的,为什么要将newNode的next指针设置为空:这行代码预防的情况主要就是链表最后一个结点的val值是我们想要排除的val值,因为在上述代码不断地遍历,尾插后,确实可以一定程度上将内容不是val的结点拎出来并插入一个新链表中,但是当我们遍历原链表至倒数第二个节点时,如果恰恰下一个结点的内容是val,我们上述的代码会不让这最后一个进入验证的循环,但最重要的是,上述代码也仅仅是没让它进入循环而已,最底层的关系中,倒数第二个结点的next指针依旧是指向这个原链表的最后一个的含有着val的结点,因此当原链表最后一个结点的val值是我们想要排除的val值时,上述代码依旧会输出这最后一个val,而这却不是我们想要看到的,因此及时止损(及时使倒数第二个结点的next指向空就显得非常重要了)

        二则是在写代码过程中对于各种不同情况的讨论,在这题里我们涉及到三处对空链表的验证,分别是传入pcur(链表的头结点的指针)时,对代表着链表的头结点的指针是否为空的验证以及最后对插入结束后对代表着尾结点的指针是否为空的验证,因为若不对这几个指针进行验证,程序运行后就无法避免的有可能遇见对空指针的解引用操作,而此类操作在C语言里是大忌

2.反转链表

(1)题目:

https://leetcode.cn/problems/reverse-linked-list/description/

(题目来源)

(2)解析:

同样,这里也有两种思路

思路一:创建新链表,遍历原链表,将原链表结点拿过来头插

思路二:创建3个结点,然后通过循环下列步骤改变各结点指向

以下是第二种思路的代码示例和一些注意点:

typedef struct ListNode 
{
	int val;
	struct ListNode* next;
	
}ListNode;

 ListNode* reverseList(struct ListNode* head)
{
	 //判空
	 if (head == NULL)
	 {
		 return head;
	 }
	 //创建三个指针
	 ListNode* n1,*n2, *n3;
	 n1 = NULL;
	 n2 = head;
	 n3 = n2->next;
	 while (n2)
	 {
		 n2->next = n1;
		 n1 = n2;
		 n2 = n3;
		 if(n3)
		 n3 = n3->next;
	 }
	 return n1;
}

这里主要有两个注意点:

        一是要注意对传入指针的判断(是否为空指针)

        二则是对n3范围的注意,也就是我倒数第二行对n3是否为空指针的判断,因为在我们一步一步的翻转过程中,n3势必要比n2快一步成为空指针,而当n2也成为空指针时,如果不对n3进行判断的话,出现就会进行对n3的解引用,也就是空指针的解引用

3.链表的中间结点

(1)题目:

https://leetcode.cn/problems/middle-of-the-linked-list/description/

(题目来源)

(2)解析:

两种思路

思路一:遍历,设置变量count来记录结点位置,直至返回(count/2)结点或其next结点

思路二:快慢指针(图解如下)

原理:2*slow=fast

具体代码:

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;

ListNode* middleNode(struct ListNode* head)
{
	//创建快慢指针
	ListNode* slow = head;
	ListNode* fast = head;
	while (fast && fast->)//注意判断顺序不能颠倒!
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	//此时slow指向的即是我们想要的中间结点
	return slow;
}

这里有一点需要注意就是while循环的结束条件之所以有两个分别是对应了我在图解里画的两种情况,前一种表示fast的next指针为空时结束,后者则是表示fast指针本身不可以为空

4.合并两个有序链表

(1)题目:

https://leetcode.cn/problems/merge-two-sorted-lists/description/

(题目来源)

(2)解析:

以下为最后一步的两种情况(即 l1 先到NULL和 l2 先到NULL)

具体代码:

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;


ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}


	ListNode* l1 = list1;
	ListNode* l2 = list2;

	ListNode* newHead, * newTail;
	newHead = newTail = NULL;

	while (l1 && l2)
	{
		if (l1->val < l2->val)
		{
			//l1拿下来尾插
			if (newHead == NULL)
			{
				newHead = newTail = l1;
			}
			else
			{
				newTail->next = l1;
				newTail = newTail->next;
			}
			l1 = l1->next;
		}
		else
		{
			//l2拿下来尾插
			if (newHead == NULL)
			{
				newHead = newTail = l2;
			}
			else
			{
				newTail->next = l2;
				newTail = newTail->next;
			}
			l2 = l2->next;

		}
	}
	//跳出循环有两种情况:l1先走到空,l2先走到空
	if (l1)
	{
		newTail->next = l2;
	}
	if (l2)
	{
		newTail->next = l1;
	}

	return newHead;
}

这里有几个重要的点:

       首先就是关于我在最上面对传入链表是否为空的讨论,这些其实并不是需要死记的东西,你看题目嘛,他的范围就明确了0的情况,也就是暗含了对空指针讨论的提示

        其次我想说的就是这个题目的具体解决方式:通过不断的对两个链表对应结点的依次比较,小的先尾插,最后分类讨论一下就行

         最后也就是最重要的还有有一点:即关于上述代码的改进

所以修改之后的代码如下:

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;


ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}


	ListNode* l1 = list1;
	ListNode* l2 = list2;

	ListNode* newHead, * newTail;
	//newHead = newTail = NULL;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));


	//改进之后:
	while (l1 && l2)
	{
		if (l1->val < l2->val)
		{
			//l1拿下来尾插
			newTail->next = l1;
			newTail = newTail->next;
			l1 = l1->next;
		}
		else
		{
			//l2拿下来尾插
		    newTail->next = l2;
		    newTail = newTail->next;
			l2 = l2->next;
		}
	}
	//跳出循环有两种情况:l1先走到空,l2先走到空
	if (l1)
	{
		newTail->next = l2;
	}
	if (l2)
	{
		newTail->next = l1;
	}

	return newHead->next;
}

同时这里还有两点需要注意:

        一.malloc申请空间之后哨兵位(也就是头结点本身存储的val值是系统给的一个随机值,只有newNode->next及之后的才是我们所求的链表,因此上述代码的返回值必须得从原来的return newHead变成return newHead->next)

        二.malloc之后必须要释放内存,但这里提交系统后后台会自动帮助我们释放内存,因此在正式的代码里,还必须加上以下几行来代替return newHead->next:

//动态申请的空间需要手动释放
ListNode* ret = newHead->next;
free(newHead);
newHead = NULL;
return ret;

5.环形链表的约瑟夫问题

(1)题目:

(2)解析:

以下是我对这道题的思考过程:

具体代码:

这道题其实跟上面讲的几道题大同小异,本质上其实也就是链表中插入和删除元素的考察,画个图仔细看看其中各个指针的指向变化就很容易可以得出基本思路了,这道题的难点也是主要就在于主函数里对排除特殊情况的讨论,这点理解了之后其他的也就迎刃而解了

6.分割链表

(1)题目:

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

(题目来源)

(2)解析:

三种思路

思路一:原链表修改

思路二:新链表修改

         通过创建新链表,大于x的往前插,小于x的往后插,就此题来说是可以解出来的,但相比第一种不仅在顺序上会出现颠倒而且还涉及了尾插和头插两种链表操作方式,代码层面上相比思路一也要麻烦不少

思路三:创建两个带头链表

具体代码:

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;


ListNode* partition(ListNode* head, int x)
{

	if (head == NULL)
	{
		return head;
	}

	//创建两个带头链表
	ListNode* lessHead, * lessTail;
	ListNode* greaterHead, * greaterTail;
	lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
	greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));

	//遍历原链表,将原链表中的结点尾插到大小链表中
	ListNode* pcur = head;
	while (pcur)
	{
		if (pcur->val < x)
		{
			//尾插到小链表中
			lessTail->next = pcur;
			lessTail = lessTail->next;
		}
		else
		{
			//尾插到大链表中
			greaterTail->next = pcur;
			greaterTail = greaterTail->next;
		}
		pcur = pcur->next;
	}
	//修改大链表的尾结点的next指向
	greaterTail->next = NULL;//给next指针初始化,若不加这一行,代码会出现死循环
	
	//使小链表的尾结点和大连表的第一个有效首结点相连(注意不是哨兵位)
	lessTail->next = greaterHead->next;

	//修改大链表的尾结点的next指针指向
	greaterTail->next = NULL;

	ListNode* ret = lessHead->next;
	free(lessHead);
	free(greaterHead);
	lessHead = greaterHead = NULL;
	return ret;
}

这题如果在自己写的时候很有可能会出现两类报错而导致程序无法成功通过oj测验的情况,下面我就来详细说说这两种报错

第一类:超出时间限制

就像上图所示的,超出时间限制大部分全都是有代码陷入死循环导致的,这里的死循环形成原因就是虽然我们设置了大小链表并且分好类,但由于大链表尾结点的指向没有更改,它就会按原来的指向再指回原链表从而造成了链表的闭环,也就是我们这里所说的死循环

第二类:使用之前未初始化

这里发生错误的原因根本就在于在题目给定的结构体中因为不包含有对next指针的初始化:

从而导致上述情况验证时next指针自动默认产生了一个随机地址(可能会导致一些不安全的问题)因此解决办法就是确保这两行代码的先后顺序

好的,这些就是我想分享的几道题目了

全文终


http://www.niftyadmin.cn/n/5795846.html

相关文章

Vue3 基础记录

Vue3 创建 基于vue-cli ## 查看vue/cli版本&#xff0c;确保vue/cli版本在4.5.0以上 vue --version## 安装或者升级你的vue/cli npm install -g vue/cli## 执行创建命令 vue create vue_test## 随后选择3.x ## Choose a version of Vue.js that you want to start the pr…

Golang学习历程【第三篇 基本数据类型类型转换】

Golang学习历程【第三篇 基本数据类型】 1. 总览2. 基本数据类型2.1 整型2.2 浮点型2.2 布尔型2.3 字符2.4 字符串2.4.1 常用定义方式2.4.2 转移字符2.4.3 常用方法2.4.3 字符串中字符替换 3. 类型转换3.1 整型与整型转化3.2 浮点数与整型转换3.3 其他类型与string类型转换3.4 …

亚马逊API接口深度解析:如何高效获取商品详情与评论数据

在当今数字化时代&#xff0c;电商平台的数据对于商家和开发者来说至关重要。亚马逊作为全球领先的电商平台&#xff0c;其API接口为开发者提供了丰富的商品信息和评论数据。本文将深入探讨如何使用亚马逊API接口获取商品详情和商品评论&#xff0c;同时提供简洁明了的使用方法…

代码随想录算法训练营第十一天-239.滑动窗口最大值

解题思想与代码实现&#xff0c;令人叹为观止队列的最佳应用从总体上讲&#xff0c;完成代码的思路是非常清晰的 根据窗口大小&#xff0c;从源数据第一个开始&#xff0c;把数据依次压入队列中从压入队列的数据中找出最大值&#xff0c;放入结果集合中再将队列中第一个元素弹出…

保姆级教程Docker部署RabbitMQ镜像

目录 1、创建挂载目录 2、运行RabbitMQ容器 3、Compose运行RabbitMQ容器 4、开启界面插件 5、查看RabbitMQ运行状态 6、常见问题处理 1、创建挂载目录 # 创建宿主机rabbitMQ挂载目录 sudo mkdir -p /data/docker/rabbitmq/log# 修改log目录权限 sudo chmod 777 /data/do…

HTML 新手易犯的标签属性设置错误

滥用target"_blank"属性&#xff1a;将所有链接的目标设为_blank会在新标签页中打开链接&#xff0c;这可能会导致用户在不知情的情况下打开大量新标签页&#xff0c;影响用户体验。正确的做法是只在需要新标签页打开的链接上使用该属性&#xff0c;并在标签中添加适…

在UE5中调用ImGui图形界面库

ImGui是一个小巧灵活、简洁美观的图形界面库 首先我们直接参考Github https://github.com/SLSNe/Unreal5-ImGui 把项目下载下来后 打开项目目录或者引擎目录 项目根目录/Plugins/ImGui/ 或 UE5引擎根目录/Engine/Plugins/ 如果没有Plugins文件夹就新建一个 把项目放里面…

CentOS 7 安装、测试和部署FastDFS

目录 FastDFS环境搭建 安装 libfastcommon 库 安装FastDFS 查看编译后的文件 FastDFS配置 FastDFS启动 启动tracker服务 启动storage服务 查看storage是否已经注册到了tracker下 查看存储文件的目录 FastDFS重启 FastDFS关闭 使用fdfs_test进行测试 修改client.co…