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，不为空则返回它的valn1 = l1 ? l1->val : 0;n2 = l2 ? l2->val : 0;//定义sum等于两节点之和加上flagint 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是否大于等于10flag = 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;}