一、两数相加
1、题目介绍
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
2、思路讲解
由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。具体而言,如果当前两个链表处相应位置的数字为 n1,n2,进位值为 carry,则它们的和为 n1+n2+carry;其中,答案链表处相应位置的数字为 (n1+n2+carry) mod 10,而新的进位值为 (n1+n2+carry)/10。
如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个 000 。
此外,如果链表遍历结束后,有 carry,还需要在答案链表的后面附加一个节点,节点的值为 carry。
3、代码实现
二、合并两个有序链表
1、题目介绍
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
2、思路讲解
先判断两个链表是否都为空,然后在创建一个新的链表,将旧链表的大小比较,一一放入新链表中。
3、代码实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
struct ListNode* head=NULL,*tail=NULL;
while(list1 && list2)
{
if(list1->val<list2->val)
{
if(head==NULL)
{
head=tail=list1;
}
else
{
tail->next=list1;
tail=tail->next;
}
list1=list1->next;
}
else
{
if(head==NULL)
{
head=tail=list2;
}
else
{
tail->next=list2;
tail=tail->next;
}
list2=list2->next;
}
}
if(list1)
{
tail->next=list1;
}
if(list2)
{
tail->next=list2;
}
return head;
}
三、环形链表(二)
1、题目介绍
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。
注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
2、思路讲解
我们定义两个指针,一个slow一个fast,slow一下走一步,fast一下走两步,如果该链表存在环,slow指针和fast指针一定会相遇
设环外链表长度为a,slow进入环后,又走了b步的距离与fast相遇,此时,设fast走完了n环,c为两指针相遇后环长减去b
fast为a+n(b+c)+b=a+(n+1)b+nc,slow=a+b,又因为fast=2slow,所以a=(n-1)b+n*c,从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。
3、代码实现
四、环形链表(一)
1、题目介绍
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
2、思路讲解
设快慢指针,慢指针一下走一步,快指针一下走二步,如果两指针相遇,则存在环。
3、代码实现
五、删除链表中的结点
1、题目介绍
有一个单链表的 head,我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的,并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意,删除节点并不是指从内存中删除它。这里的意思是:
给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。
自定义测试:
对于输入,你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点,而应该是链表中的一个实际节点。
我们将构建链表,并将节点传递给你的函数。
输出将是调用你函数后的整个链表。
2、思路讲解
思路一:讲node结点的后面的结点的值拷贝给node,并将node的下一个结点指向node的next的next
思路二:定义一个cur指针,指向node,并将node指向下一个结点,然后拷贝给cur
3、代码实现
思路一
思路二
六、环形链表中的约瑟夫问题
1、题目介绍
文章来源:https://www.toymoban.com/news/detail-720160.html
2、思路讲解
先创建一个链表,然后一一赋值,定义一个cur指针指向头结点,如果到了m的时候,prev指向cur的后结点并且释放掉cur,并且cur指向prev的next,如果不到m,讲prev指向cur,cur在指向cur的next,循环终止的条件是,cur的下一个结点就是cur,代表只有最后一个人了。文章来源地址https://www.toymoban.com/news/detail-720160.html
3、代码实现
typedef struct ListNode ListNode;
ListNode* BuyNode(int i)
{
ListNode* newnode=malloc(sizeof(ListNode));
if(newnode==NULL)
{
exit(-1);
}
newnode->next=NULL;
newnode->val=i;
return newnode;
}
ListNode* Create(int n)
{
ListNode* head,*tail;
int i=1;
head=tail=BuyNode(i++);
while(i<=n)
{
tail->next=BuyNode(i++);
tail=tail->next;
}
tail->next=head;
return head;
}
int ysf(int n, int m ) {
ListNode* head=Create(n);
ListNode* prev=NULL;
ListNode* cur=head;
int i=1;
while(cur!=cur->next)
{
if(i==m)
{
prev->next=cur->next;
free(cur);
cur=prev->next;
i=1;
}
else
{
prev=cur;
cur=cur->next;
i++;
}
}
return cur->val;
}
到了这里,关于经典链表试题(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!