【Leetcode -141.环形链表 -2.两数相加】
【Leetcode -141.环形链表 -2.两数相加】
Leetcode -141.环形链表
题目：给你一个链表的头节点 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;
}Leetcode -2.两数相加
题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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;
}腾讯云开发者
