题目:给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。
示例 2: 输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。
示例 3: 输入:head = [1], pos = -1 输出:false 解释:链表中没有环。
提示: 链表中节点的数目范围是 [0, 10^4] -10^5 <= Node.val <= 10^5 pos 为 -1 或者链表中的一个 有效索引 。
我们的思路是快慢指针,定义两个指针fast和slow,fast每次走两步,slow每次走一步,如果有环的话,fast一定能追上slow;如图:
fast走两步,slow走一步:
fast走两步,slow走一步:
最终fast追上slow,即它们相等的时候;
代码:
bool hasCycle(struct ListNode *head)
{
struct ListNode *fast = head,*slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
return true;
}
}
return false;
}
题目:给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1: 输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807.
示例 2: 输入:l1 = [0], l2 = [0] 输出:[0]
示例 3: 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1]
提示: 每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零
我们的思路是,将链表逐一相加拿下来,计算两个结点val之和,因为每个结点只能存放0-9的数字,所以每十进一,用flag来存放这个一,所以两个结点val之和加上flag,再取余才是拿下来放进新链表的val;当两个链表都空了,如果flag中还留着一,那么要再开辟一个结点,val为1,放到新链表的尾部;
如图,第一次相加:
第二次相加,n1+n2 = 10,需要进一,所以flag在相加完后变成1;
第三次相加:
当两个链表都走完,但是上两个结点相加进10,flag还留了个1,所以要再开辟一个结点,存放1,把它放到链表的尾部;
最后的结果:
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* tail = NULL, * head = NULL;
int flag = 0, n1, n2;
//当l1或者l2其中一个不为空时继续
while (l1 || l2)
{
//判断l1或者l2是否为空,为空则返回0,不为空则返回它的val
n1 = l1 ? l1->val : 0;
n2 = l2 ? l2->val : 0;
//定义sum等于两节点之和加上flag
int sum = n1 + n2 + flag;
//初次相加
if (tail == NULL)
{
struct ListNode* p = malloc(sizeof(struct ListNode));
tail = head = p;
tail->val = sum % 10;
tail->next = NULL;
}
//非初次相加
else
{
struct ListNode* p = malloc(sizeof(struct ListNode));
p->val = sum % 10;
p->next = NULL;
tail->next = p;
tail = tail->next;
}
//flag取sum的商,即判断sum是否大于等于10
flag = sum / 10;
//如果l1不为空,l1继续迭代
if (l1)
{
l1 = l1->next;
}
//如果l2不为空,l2继续迭代
if (l2)
{
l2 = l2->next;
}
}
//若上一次相加的进一还没处理,就直接开辟一个结点,val为1,放到链表的尾部
if (flag == 1)
{
struct ListNode* p = malloc(sizeof(struct ListNode));
p->val = 1;
p->next = NULL;
tail->next = p;
}
return head;
}