LeetCode-21.合并两个有序链表（链表+递归）

2024-01-30 22:57:10

题目内容

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

题解

个人题解（一）：

/**
 * 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* l1, ListNode* l2) {
        if (l1 == nullptr){
            return l2;
        }
        else if (l2 == nullptr){
            return l1;
        }
        else if (l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

执行结果

执行结果：通过
执行用时：8 ms, 在所有 C++ 提交中击败了64.41%的用户
内存消耗：14.4 MB, 在所有 C++ 提交中击败了82.89%的用户

复杂度分析

时间复杂度： O ( n + m ) O(n+m) O(n+m)，其中 n n n 和 m m m 分别为两个链表的长度。因为每次调用递归都会去掉 l 1 l1 l1 或者 l 2 l2 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O ( n + m ) O(n+m) O(n+m)。
空间复杂度： O ( n + m ) O(n+m) O(n+m)，其中 n n n 和 m m m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n + m n+m n+m 次，因此空间复杂度为 O ( n + m ) O(n+m) O(n+m).

注解：

参考链接

线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构
非线性结构：不满足线性结构的数据结构

链表（单项链表的建立、删除、插入、打印）

链表一般分为：单向链表、双向链表、环形链表
基本概念
链表实际上是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，且链表的长度不是固定的，链表数据的这一特点使其可以非常方便地实现节点的插入和删除操作。
链表的每个元素称为一个节点，每个节点都可以存储在内存的不同位置，为了表示每个元素与后继元素的逻辑关系，以便构成“一个节点链着一个节点”的链式存储结构，除了存储元素本身的信息外，还要存储其直接后继信息。因此，每个节点都包含两个部分，第一部分称为链表的数据区域，用于存储元素本身的数据信息，这里用data表示，它不局限于一个成员数据，也可是多个成员数据；第二部分是一个结构体指针，称为链表的指针域，用于存储其直接后继的节点信息，这里用next表示。next的值实际上就是下一个节点的地址，当前节点为末节点时，next的值设为空指针。
```
struct link
{
	int data;
	struct link *next;
}
```
像上面这种只包含一个指针域、由n个节点链接形成的链表，就称为线性链表或者单向链表，链表只能顺序访问，不能随机访问，链表这种存储方式最大的缺点就是容易出现断链，一旦链表中某个节点的指针域数据丢失，那么意味着将无法找到下一个节点，该节点后面的数据将全部丢失。
链表与数组比较
数组（包括结构体数组）的实质是一种线性表的顺序表示方式，它的优点是使用直观，便于快速、随机地存取线性表中的任一元素，但缺点是对其进行插入和删除操作时需要移动大量的数组元素，同时由于数组属于静态内存分配，定义数组时必须指定数组的长度，程序一旦运行，其长度就不能再改变，实际使用个数不能超过数组元素最大长度的限制，否则就会发生下标越界的错误，低于最大长度时又会造成系统资源的浪费，因此空间效率较差。

单向链表的建立

#include <stdio.h>
#include <stdlib.h>

struct link *AppendNode(struct link *head);
void DisplyNode(struct link *head);
void DeletMemory(struct link *head);

struct link
{
	int data;
	struct link *next;
};

int main(void)
{
	int i = 0;
	char c;
	struct link *head = NULL;  //链表头指针
	printf("Do you want to append a new node(Y/N)?");
	scanf_s(" %c", &c);
	while (c == 'Y' || c == 'y' )
	{
		head = AppendNode(head);  //向head为头指针的链表末尾添加节点
		DisplayNode(head);  //显示当前链表中的各节点信息
		printf("Do you want to append a new node(Y/N)?");
		scanf_s(" %c", &c);
		i++;
	}
	printf("%d new nodes have been appended", i);
	DeleteMemory(head);  //释放所有动态分配的内存
	
	return 0;
}

/* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */
struct link *AppendNode(struct link *head)
{
	struct link *p = NULL, *pr = head;
	int data;
	p = (struct link *)malloc(sizeof(struct link));  //让p指向新建的节点
	if (p == NULL)  //若新建节点申请内存失败，则退出程序
	{
		printf("No enoug memory to allocate\n");
		exit(0);
	}
	if (head == NULL)  //若原链表为空链表
	{
		head = p;  //将新建节点置为头节点
	}
	else  //若原链表为非空，则将新建节点添加到表尾
	{
		while (pr->next != NULL)  //若未到表尾，则移动pr直到pr指向表尾
		{
			pr = pr->next;  //让pr指向下一个节点
		}
		pr-next = p;  //让末节点的指针指向新建的节点
	}
	printf("Input node data\n");
	scanf_s("%d", &data);  //输入节点数据
	p->data = data;  //将新建节点的数据域赋值为输入的节点数据值
	p->next = NULL;  //将新建的节点置为表尾
	return head;  //返回添加节点后的链表的头指针
}

/* 函数的功能：显示链表中所有节点的节点号和该节点中的数据项的内容 */
void DisplayNode(struct link *head)
{
	struc link *p = head;
	int j = 1;
	while (p != NULL)  //若不是表尾，则循环打印节点的数值
	{
		printf("%5d%10d\n", j, p->data);  //打印第j个节点数据
		p = p->next;  //让p指向下一个节点
		j++;
	}
}

/* 函数的功能：释放head所指向的链表中所有节点占用的内存 */
void DeletMemory(struct link *head)
{
	struct link *p = head, *pr = NULL;
	while (p != NULL)  //若不是表尾，则释放节点占用的内存
	{
		pr = p;       //在pr中保存当前节点的指针
		p = p->next;  //让p指向下一个节点
		free(pr);     //释放pr指向的当前节点占用的内存
	}
}

上面的代码使用了三个函数AppendNode、DisplayNode、DeletMemory。
struct link *AppendNode (struct link *head);（函数作用：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针）；
void DisplyNode (struct link *head);（函数功能：显示链表中所有节点的节点号和该节点中的数据项的内容）；
void DeletMemory (struct link *head);（函数功能：释放head所指向的链表中所有节点占用的内存）；
（还使用了malloc函数和free函数）

malloc函数
作用：用于分配若干字节的内存空间，返回一个指向该内存首地址的指针，若系统不能提供足够的内存单元，函数将返回空指针NULL，函数原型为void *malloc(unsigned int size).
其中，size是表示向系统申请空间的大小，函数调用成功将返回一个指向void的指针（void * 指针是ANSIC新标准中增加的一种指针类型，具有一般性，通常称为通用指针或者无类型的指针）常用来说明其基类型未知的指针，即声明了一个指针变量，但未指定它可以指向哪一种基类型的数据。因此，若要将函数调用的返回值赋予某个指针，则应先根据该指针的基类型，用强转的方法将返回的指针值强转为所需的类型，然后再进行赋值
```
int *pi;
pi = (int *)malloc(4);
```
其中，malloc(4)表示申请一个大小为4字节的内存，将malloc(4)返回值的void * 类型强转为int * 类型后再赋值给int型指针变量pi, 即用int型指针变量pi指向这段存储空间的首地址。若不能确定某种类型所占内存的字节数，则需使用sizeof()计算本系统中该类型所占的内存字节数，然后再用malloc()向系统申请相应字节数的存储空间。
```
pi = (int *)malloc(sizeof(int));
```
free函数
释放向系统动态申请的由指针p指向的内存存储空间，其原型为：Void free(void *p); 该函数无返回值，唯一的形参p给出的地址只能由malloc()和calloc()申请内存时返回的地址。该函数执行后，将以前分配的指针p指向的内存返还给系统，以便系统重新分配。
为什么要用free释放内存？
在程序运行期间，用动态内存分配函数来申请的内存都是从堆上分配的，动态内存的生存期由程序员自己来决定，使用非常灵活，但也易出现内存泄漏的问题。为了防止内存泄露的发生，程序员必须及时调用free()释放已不再使用的内存。
单向链表的删除操作
删除操作就是将一个待删除的节点从链表中断开，不再与链表的其他节点有任何联系。
需要考虑四种情况：
（1）若原链表为空表，则无需删除节点，直接退出程序
（2）若找到的待删除节点p是头节点，则将head指向当前节点的下一个节点(p->next)，即可删除当前节点
（3）若找到的待删除节点不是头节点，则将前一节点的指针域指向当前节点的下一节点(pr->next = p->next)，即可删除当前节点；当待删除节点是末节点时，由于p->next值为NULL，因此执行pr->next = p->next后，pr->next的值也变成NULL，从而使pr所指向的节点由倒数第二个节点变成了末节点
（4）若已搜索到表尾（p->next == NULL），仍未找到待删除节点，则显示“未找到”。
注意：节点被删除后，只是将它从链表中断开而已，它仍占用着内存，必须释放其所占的内存，否则将出现内存泄露。
（头节点不是头指针，注意两者区别！）

头节点和头指针
头指针存储的是头节点内存的首地址，头节点的数据域可以存储如链表长度等附加信息，也可以不存储任何信息。
参考链接–头指针和头节点：
结构之美：单链表的头结点与头指针
 链表头结点与头指针
 链表、头指针、头结点
 单链表头节点，头指针
LeetCode-21.合并两个有序链表（链表+递归）
值得注意的是：
（1）无论链表是否为空，头指针均不为空。头指针是链表的必要元素；
（2）链表可以没有头节点，但不能没有头指针，头指针是链表的必要元素；
（3）记得使用free释放内存。
单向链表的删除操作实现

struct link *DeleteNode(struct link *head, int nodeData)
{
	struct link *p = head, *pr = head;
	if (head == NULL)
	{
		printf("Linked table if empty!\n");
		return 0;
	}
	//搜索要删除的数据元素nodedata
	while (nodedata != p->data && p->next != NULL)
	{
		pr = p;  //pr保存当前节点
		p = p->next;  //p指向当前节点的下一节点
	}
	if (nodedata == p->data)
	{
		if (p == head)  //如果待删除节点为头节点（注意头指针和头节点的区别）
		{
			head = p->next;
		}
		else  //如果待删除不是头节点
		{
			pr->next = p->next;
		}
		free(p);  //释放已删除节点的内存
	}
	else  //未发现节点值为nodeData的节点
	{
		printf("This Node has not been found");
	}
	return head;
}

单向链表的插入
向链表中插入一个新的节点时，首先要新建一个节点，将其指针域赋值为空指针（p->next = NULL），然后在链表中寻找适当的位置执行节点的插入操作。
此时需要考虑以下四种情况：
（1）若原链表为空，则将新节点p作为头节点，让head指向新节点p(head = p)
（2）若原链表为非空，则按节点值的大小（假设节点值已按升序排序）确定插入新节点的位置，若在头节点前插入新节点，则将新节点的指针域指向原链表的头节点（p->next = head），且让head指向新节点(head = p)
（3）若在链表中间插入新节点，则将新节点的指针域指向下一节点（p->next = pr->next），且让前一节点的指针域指向新节点（pr->next = p）
（4）若在表尾插入新节点，则末节点指针域指向新节点（p->next = p）
单向链表的插入操作实现

/*函数功能：向单向链表中插入数据 按升序排列*/
struct link *InsertNode(struct link *head, int nodeData)
{
	struct link *p = head, *pr = head, *temp = NULL;
	p = (struct link *)malloc(sizeof(struct link));
	if (p === NULL)
	{
		printf("No enough memory!\n");
		exit(0);
	}
	p->next = NULL;  //待插入节点指针域赋值为空指针
	p->data = nodeData;
	if (head == NULL)  //若原链表为空
	{
		head = p;  //插入节点作为头节点
	}
	else  //原链表不为空
	{
		while (pr->data < nodeData && pr->next != NULL)
		{
			temp = pr;  //保存当前节点的指针
			pr = pr->next;  //pr指向当前节点的下一节点
		}
		if (pr->data >= nodeData)
		{
			if (pr == head)  //在头节点前插入新节点
			{
				p->next = head;  //新节点指针域指向原链表头节点
				head = p;  //头指针指向新节点
			}
			else
			{
				pr = temp;
				p->next = pr->next;  //新节点指针域指向下一节点
				pr-next = p;  //让前一节点指针域指向新节点
			}
		}
		else   //若在表尾插入新节点
		{
			pr->next = p;  //末节点指针域指向新节点
		}
	}
	return head;
}

码农公寓

题目内容

题解

个人题解（一）：

执行结果

复杂度分析

注解：

链表（单项链表的建立、删除、插入、打印）

相关文章