接着我们介绍后面的三道题,虽然代码变多了但我们的思路更加通顺了
4. 单链表相关经典算法OJ题3:合并两个有序链表
题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/
创建新链表,遍历原链表,将节点值小的进行尾插到新链表中
这里要多次进行对NULL的判断,开始传入列表,中间newHead的判断,循环出来一个为NULL的判断
重复原因:新链表存在空链表和非空两种情况
优化的方法:
1.将重复的部分封装成一个函数
2.动态申请一个空间但这个空间部存储任何的信息
那么我们着重讲一下第二个方法:
他的解决方法就是让新链表不为NULL
在创建时动态申请一块空间,但不存储任何数据,让NULL节点变为非NULL的节点,这是就不用判断链表是不是为非NULL
但这时返回就不能将头节点直接返回,而是要将头节点的下一个位置的地址返回
当然释放的空间还是要释放一下,来使代码更加完善
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
ListNode* l1 = list1;
ListNode* l2 = list2;
//判空
if(list1 == NULL)
{
return list2;
}
if(list2 == NULL)
{
return list1;
}
ListNode* newHead,*newTail;
//newHead = newTail = NULL;
newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
while(l1 && l2)
{
if(l1->val < l2->val)
{
newTail->next = l1;
newTail = newTail->next;
l1 = l1->next;
}
else
{
newTail->next = l2;
newTail = newTail->next;
l2 = l2->next;
}
}
//跳出循环有两种情况
if(l2 != NULL)
{
newTail->next = l2;
}
if(l1 != NULL)
{
newTail->next = l1;
}
ListNode* ret = newHead->next;
free(newHead);
newHead = NULL;
return ret;
}
其实这样的链表叫带头链表,这个“头”一般称作哨兵位
5. 循环链表经典应⽤-环形链表的约瑟夫问题
题目链接:https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a
思路一:用数组的方法,先进行遍历然后将离开的人置为0,然后不断循环遍历最中不为0的就是我们要的数据
思路二:循环链表的方法
我们先介绍一下循环链表:
这里涉及到循环链表,其实也就是单链表但是尾部相连了
那么在创建和删除时要多注意就行了
循环数数,将数到2的,将其删除
这里就要使用前后指针
代码的难点就是创建循环链表文章来源:https://www.toymoban.com/news/detail-852492.html
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param n int整型
* @param m int整型
* @return int整型
*/
#include <stdio.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* createCircle(int n)//创建带环链表
{
//创建第一个节点
ListNode* phead = buyNode(1);
ListNode* ptail = phead;
for(int i = 2; i <= n;i++)
{
ptail->next = buyNode(i);
ptail = ptail->next;
}
ptail->next = phead;
return ptail;
}
int ysf(int n, int m ) {
// write code here
ListNode* prev = createCircle(n);
ListNode* pcur = prev->next;
int count = 1;
while (prev->next != pcur)//链表只有一个节点
{
if(count == m)
{
//销毁,先连接,在销毁
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;
}
else
{
prev = pcur;
pcur = pcur->next;
count++;
}
}
return pcur->val;
}
6. 单链表相关经典算法OJ题5:分割链表
题目链接:https://leetcode.cn/problems/partition-list-lcci/description/
思路一:将原列表复制一份,然后对大于等于x的进行操作,先尾插后销毁
思路二:或者创建一个新链表进行存储,对大于的数进行尾插,小于的进行头插
思路三:创建两个新链表:小链表和大链表
分成两个链表然后将两个链表连接起来
这里就是greaterHead后的指针不为NULL,而是一个随机地址
将两个代码换过来,就可以解决这个问题了
文章来源地址https://www.toymoban.com/news/detail-852492.html
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* partition(struct 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;
}
//首尾相连
greaterTail->next = NULL;
lessTail->next = greaterHead->next;
ListNode* ret = lessHead->next;
free(lessHead);
free(greaterHead);
lessHead = greaterHead = NULL;
return ret;
}
到了这里,关于C语言简单的数据结构:单链表的有关算法题(2)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!