题目练习之链表那些事儿

用户11352420

发布于 2024-11-07 21:37:32

310

发布于 2024-11-07 21:37:32

文章被收录于专栏：编程学习

前面我们知道了单链表的结构及其一些数据操作，今天我们来看看有关于单链表的题目~

移除链表元素

移除链表元素： https://leetcode.cn/problems/remove-linked-list-elements/description/

这个题目要求我们删除链表中是指定数据的结点，最终返回新的头结点，结合例子来看看。

示例1中删除了数据为6的结点，输出新的链表数据，我们可以怎么做呢？

首先来看看第一个方法

思路1

遍历链表找到值为val的结点，执行删除指定位置的操作，返回头结点

简单回顾单链表的删除pos结点操作我们可以进行更快的操作。

我们可以看到题目代码中已经给出了单链表的结构，只需要我们在函数中实现相应的操作就可以了。为了使用方便，我们可以将结构体使用typedef重命名一下：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
	ListNode* pcur = head;//遍历链表
	while(pcur)
	{
		//看是不是指定数据的结点
		//是就执行删除指定结点的操作
		if (pcur->val == val)
		{
			ListNode* pos = pcur;
			pcur = pcur->next;
             //易错点！！！
			//pcur直接往后面走，避免被释放
			if (pos == head)//头删
			{
				ListNode* next = pos->next;
				free(head);
				head = next;
				//原来头结点的下一个结点成为新的头结点
			}
			else
			{
				//遍历链表找指定结点的上一个结点
				ListNode* prev = head;
				while (prev->next != pos)
				{
					prev = prev->next;
				}
				//删除pos结点
				//改变上一个结点指向
				prev->next = pos->next;
				free(pos);
				pos = NULL;//释放及时置为空，避免野指针
			}
		}
		else
		{
			pcur = pcur->next;
		}//不是往后面继续遍历
	}
    //返回头结点
    //在原来的链表操作，头结点没有变化
	return head;
}

提交成功

这里有一个易错点就是当遍历到是指定数据的结点时，pcur要直接往后面走，用pos保存当前结点，这样能避免后面释放掉pcur，就不能正常使用了。
我们可以看到思路1有两层while循环，外层循环进行遍历找结点，内层循环删除指定的结点，那么时间复杂度也就是O（N^2),显然这不是最好的方案，我们有没有什么更好的方法呢？接下来，就是我们的思路二。

思路2

创建一个新的链表，遍历原来的链表，将链表中值不为val的结点尾插到新链表中，这个新链表呢，最开始创建两个新结点——NewHead、NewTail并且把它们置为空指针。

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
	ListNode* NewHead = NULL;//新的头结点
	ListNode* NewTail = NULL;//新的尾结点

	//遍历原来的链表
	ListNode* pcur = head;
	while (pcur)//结点不为空
	{
		//将结点数据不等于val的放入新链表
		if (pcur->val != val)
		{
			//尾插
			//1.如果链表为空
			//新的头结点和尾结点就是当前的结点
			if (NewHead == NULL)
			{
				NewHead = NewTail = pcur;
			}
			//2.链表不为空
			else 
			{
				//新链表原来尾结点的下一个结点就是当前的结点
				NewTail->next = pcur;
				//当前结点成为新的尾结点
				NewTail = pcur;
			}
		}
		//继续往后面遍历
		pcur = pcur->next;
	}
	//易错点！！！
	//如果尾结点不为空，要把尾结点置为空
	if (NewTail)
	{
		NewTail->next = NULL;
	}
    //返回新的头结点
	return NewHead;
}

提交成功

这里有一个易错点就是要把尾结点的下一个结点置为空，如果不把尾结点的下一个结点置为空，尾结点本身的内容（保存的数据和下一个结点的指针）并没有发生改变，链表依然会带上尾结点后面的数据，比如示例1中1，2，6，3，4，5，6.当新的尾结点是5的时候，后面会带一个结点，而我们希望的是尾结点后面就没有结点了，所以我们要把尾结点的下一个结点置为空。当然，在置为空以前，首先要判断尾结点是否为空，避免对空指针进行解引用。

合并两个有序链表

合并两个有序链表： https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目同样给出了链表结构，我们可以直接使用

这个题目看起来是不是有一点眼熟，在前面我们练习过合并两个有序数组，这里是合并两个有序链表，我们知道链表在物理结构上不一定是连续的，那我们可以怎么样解决这个问题呢？

我们一起来看看下面的思路

思路

创建一个新链表，分别遍历两个链表，比较结点大小，把小的尾插到新链表中，当一个链表走到结尾，把另外一个链表剩下的结点尾插到新链表中。

代码实现：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	//特殊处理其中一个链表为空，避免后面对newTail空指针解引用
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}
	//创建新链表
	ListNode* newHead = NULL;
	ListNode* newTail = NULL;

	//遍历两个链表比较
	ListNode* pcur1 = list1;
	ListNode* pcur2 = list2;

	//小的尾插到新链表中
	//一个链表到末尾就结束循环
	while (pcur1 && pcur2)
	{
		//链表1结点小尾插到新链表中
		if (pcur1->val < pcur2->val)
		{
			//新链表为空
			if (newHead == NULL)
			{
				newHead = newTail = pcur1;
			}
			else
			{
				//原来尾结点下一个结点指向pcur1
				newTail->next = pcur1;
				//pcur1成为新的尾结点
				newTail = pcur1;
			}
			//pcur1继续往后面遍历
			pcur1 = pcur1->next;
		}

		//链表2结点小尾插到新链表中
		else
		{
			//新链表为空
			if (newHead == NULL)
			{
				newHead = newTail = pcur2;
			}
			else
			{
				//原来尾结点下一个结点指向pcur2
				newTail->next = pcur2;
				//pcur2成为新的尾结点
				newTail = pcur2;
			}
			//pcur2继续往后面遍历
			pcur2 = pcur2->next;
		}
	}
	//！！！一定是一个链表先走到空
	//一个链表已经走到空，尾插另外一个链表剩下的结点
	if (pcur1)
	{
		newTail->next = pcur1;
	}
	//不需要循环,链表结构有保存后面的结点
	if (pcur2)
	{
		newTail->next = pcur2;
	}
	//返回头结点
	return newHead;
}

提交通过，这个思路是正确的，但是这里的代码有点长，有没有什么重复地方可以优化一下呢？

优化

我们可以看到判断新链表为空是在重复的，我们可以向操作系统借空间，让新链表不为空直接进行尾插操作，这里我们向操作系统借的空间就可以理解为一个哨兵位，是用来占位置的。

优化代码：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	//特殊处理其中一个链表为空，避免后面对newTail空指针解引用
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}
	//创建新链表
	ListNode* newHead, * newTail;
	//向操作系统借空间
	//！！！使用结束记得释放还给操作系统
	newHead = newTail = (ListNode*)malloc(sizeof(ListNode));

	//遍历两个链表比较
	ListNode* pcur1 = list1;
	ListNode* pcur2 = list2;

	//小的尾插到新链表中
	//一个链表到末尾就结束循环
	while (pcur1 && pcur2)
	{
		//链表1结点小尾插到新链表中
		if (pcur1->val < pcur2->val)
		{
			//原来尾结点下一个结点指向pcur1
			newTail->next = pcur1;
			//pcur1成为新的尾结点
			newTail = pcur1;
			//pcur1继续往后面遍历
			pcur1 = pcur1->next;
		}

		//链表2结点小尾插到新链表中
		else
		{
			//原来尾结点下一个结点指向pcur2
			newTail->next = pcur2;
			//pcur2成为新的尾结点
			newTail = pcur2;
			//pcur2继续往后面遍历
			pcur2 = pcur2->next;
		}
	}
	//！！！一定是一个链表先走到空
	//一个链表已经走到空，尾插另外一个链表剩下的结点
	if (pcur1)
	{
		newTail->next = pcur1;
	}
	//不需要循环,链表结构有保存后面的结点
	if (pcur2)
	{
		newTail->next = pcur2;
	}
	//保存新链表头结点下一个结点（真正的头结点）
	ListNode* next = newHead->next;
	//释放掉动态申请的内存空间
	free(newHead);
    //newHead、newTail指向同一块内存，只需要释放一次就可以，多次释放会报错
	newHead = NULL;
	return next;
}