数据结构练习题（链表）

1合并两个有序链表

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

示例 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 均按 非递减顺序 排列

思路：

1. 初始检查：

   • 首先检查两个链表是否为空。如果其中一个链表为空，直接返回另一个链表。

2. 创建哑节点：

   • 创建一个哑节点（dummy node），用于简化链表的插入操作。哑节点的 next 指针将最终指向新链表的头结点。

3. 合并链表：

   • 使用 while 循环，在 list1 和 list2 都不为空时，比较两个链表当前节点的值，将较小的节点添加到新链表的尾部，并移动相应的指针。
   • newtail 始终指向新链表的最后一个节点，以便于插入新节点。

4. 处理剩余节点：

   • 循环结束后，可能其中一个链表还剩下一些节点。将剩余的节点直接添加到新链表的尾部。

5. 返回结果：

   • 返回哑节点的 next 指针，即新链表的头结点，跳过哑节点本身。

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){// 如果 list1 为空，直接返回 list2if(list1 == NULL){return list2;}// 如果 list2 为空，直接返回 list1if(list2 == NULL){return list1;}// 创建一个哑节点（dummy node），用于简化链表操作struct ListNode dummy;// 新链表的尾部始终指向哑节点struct ListNode* newtail = &dummy;// 初始化哑节点的 next 指针dummy.next = NULL;// 当 list1 和 list2 都不为空时，循环比较并合并while(list1 && list2){// 如果 list1 的值小于 list2 的值if(list1->val < list2->val){// 将 list1 的节点添加到新链表的尾部newtail->next = list1;// 移动 list1 指针list1 = list1->next;} else {// 如果 list2 的值小于或等于 list1 的值// 将 list2 的节点添加到新链表的尾部newtail->next = list2;// 移动 list2 指针list2 = list2->next;}// 移动新链表的尾部指针newtail = newtail->next;}// 处理剩余的节点// 如果 list1 不为空，将剩余的 list1 节点添加到新链表的尾部if(list1){newtail->next = list1;} else {// 如果 list2 不为空，将剩余的 list2 节点添加到新链表的尾部newtail->next = list2;}// 返回新链表的头结点（跳过哑节点）return dummy.next;
}

2环形链表的约瑟夫问题

题目背景：著名的Josephus问题 据说著名犹太 Josephus有过以下的故事：在罗⻢⼈占领乔塔帕特后，39个犹太⼈与 Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被⼈抓到，于是决定了⼀个⾃杀 ⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀ 个重新报数，直到所有⼈都⾃杀⾝亡为⽌。 历史学家 然⽽Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在 第16个与第31个位置，于是逃过了这场死亡游戏。

题目描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 1≤n,m≤100001≤n,m≤10000

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

示例1

输入：

5,2     

复制返回值：

3    

复制说明：

开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3     

思路：

1. 创建环形链表：

   • 调用 createList(n) 函数创建一个包含 n 个节点的环形链表。

2. 初始化指针和计数器：

   • pre 指针指向链表的最后一个节点。
   • cur 指针指向 pre 的下一个节点（即头节点）。
   • 初始化计数器 count 为 1。

3. 遍历链表并删除节点：

   • 当链表中还有多个节点时，循环遍历链表。
   • 如果计数器 count 等于 m，则删除当前节点，并重置计数器。

4. 约瑟夫环问题求解：

   • ysf(int n, int m) 函数用于解决约瑟夫环问题。
   • 创建一个包含 n 个节点的环形链表。
   • 使用 pre 指针指向当前节点的前一个节点，cur 指针指向当前节点。
   • 当链表中还有多个节点时，循环遍历链表，并使用计数器 count 记录当前的位置。
   • 当计数器达到 m 时，销毁当前节点，并调整指针，重新开始计数。
   • 当链表中只剩下一个节点时，返回该节点的值。

代码：

#include <stdlib.h>// 定义链表节点结构
typedef struct ListNode ListNode;// 购买新节点
ListNode* buyNode(int x) {ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL) {exit(1); // 内存分配失败，退出程序}node->val = x;node->next = NULL;return node;
}// 创建带环的链表
ListNode* createList(int n) {ListNode* head = buyNode(1); // 创建头节点ListNode* tail = head;//刚开始只有一个结点，即是头结点也是为节点for (int i = 2; i <= n; i++) {//开始尾插tail->next = buyNode(i); // 创建并链接新节点tail = tail->next; // 移动尾指针}tail->next = head; // 最后一个节点的 next 指针指向头节点，形成环return tail; // 返回尾节点，方便操作
}// 约瑟夫环问题求解
int ysf(int n, int m) {// 创建一个有 n 个节点的环形链表ListNode* pre = createList(n);先知道尾结点ListNode* cur = pre->next; // 当前节点是前一个结点的next域处int count = 1;// 当链表中还有多个节点时while (cur->next != cur) {if (count == m) {// 销毁当前节点pre->next = cur->next;//销毁结点的前一个结点，指向销毁结点的后一个结点free(cur);cur = pre->next; // 重新定位当前节点count = 1; // 因为销毁 m 节点后要从其下一个节点接着开始} else {// 此时不需要删除节点pre = cur;cur = cur->next;count++;}}// 返回最后剩下的节点的值return cur->val;
}

3.04. 分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

思路：

1. 初始检查：

   • 首先检查链表是否为空。如果链表为空，直接返回头节点。

2. 创建哑节点：

   • 创建两个哑节点 lessHead 和 bigHead，分别用于存放小于 x 和大于等于 x 的节点。
   • lessTail 和 bigTail 分别指向各自链表的尾部，用于插入新节点。

3. 遍历链表并分区：

   • 遍历原链表，根据当前节点的值将节点插入到相应的链表中。
   • 如果当前节点的值小于 x，则将其插入到较小值链表的尾部。
   • 如果当前节点的值大于等于 x，则将其插入到较大值链表的尾部。

4. 连接两个链表：

   • 将较大值链表的尾部指向 NULL，防止成环。
   • 将较小值链表的尾部指向较大值链表的头部，完成分区。

5. 返回结果：

   • 释放哑节点占用的内存。
   • 返回最终链表的头节点（跳过较小值链表的哑节点）。

代码：

typedef struct ListNode ListNode;struct ListNode* partition(struct ListNode* head, int x) {// 如果链表为空，直接返回if (head == NULL) {return head;}// 创建两个哑节点分别用于存放小于 x 和大于等于 x 的节点ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));ListNode* lessTail = lessHead;ListNode* bigHead = (ListNode*)malloc(sizeof(ListNode));ListNode* bigTail = bigHead;// 遍历原链表ListNode* cur = head;while (cur) {if (cur->val < x) {// 如果当前节点的值小于 x，将其添加到较小值链表的尾部lessTail->next = cur;lessTail = lessTail->next;} else {// 如果当前节点的值大于等于 x，将其添加到较大值链表的尾部bigTail->next = cur;bigTail = bigTail->next;}cur = cur->next; // 移动到下一个节点}// 在原来链表中大链表的的值可能指向的是数据域的，所有将较大值链表的尾部指向 NULL，防止成环 若不加这项代码会出现死循环 bigTail->next = NULL;// 将较小值链表的尾部指向较大值链表的头部lessTail->next = bigHead->next;// 获取最终链表的头节点ListNode* ret = lessHead->next;// 释放哑节点占用的内存free(lessHead);free(bigHead);lessHead=bigHead=NULL;// 返回最终链表的头节点return ret;
}