Leetcode:相交链表，环形链表，环形链表||
Leetcode:相交链表，环形链表，环形链表||
💡相交链表
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
思路：
先分别遍历两个链表，得出两个链表的节点个数和两个链表节点数的差，再创建两个指针指向两个链表，让节点数较多的链表的指针先遍历这个差值的节点数，然后两个指针再同时遍历，当两个指针指向的节点的地址相同时，说明两个链表相交，且此节点为交点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
ListNode* curA=headA;
ListNode* curB=headB;
int lenA=0;
int lenB=0;
while(curA->next)
{
curA=curA->next;
lenA++;
}
while(curB->next)
{
curB=curB->next;
lenB++;
}
int n=abs(lenA-lenB);
ListNode* longlist=headA;
ListNode* shortlsit=headB;
if(lenA<lenB)
{
longlist=headB;
shortlsit=headA;
}
while(n)
{
longlist=longlist->next;
n--;
}
while(longlist&&shortlsit)
{
if(longlist==shortlsit)
return longlist;
longlist=longlist->next;
shortlsit=shortlsit->next;
}
return NULL;
}💡
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
思路：
先创建两个指针（cur1，cur2）指向头节点来遍历这个链表，其中一个指针每次走一个节点，一个指针每次走两个节点，如果链表中有环，则两个指针一定会相遇，即cur1==cur2
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
if(head==NULL)
return false;
ListNode*cur1=head;
ListNode*cur2=head;
while(cur2&&cur2->next)
{
cur1=cur1->next;
cur2=cur2->next->next;
if(cur1==cur2)
return true;
}
return false;
}💡
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
if(head==NULL)
return NULL;
ListNode*cur1=head;
ListNode*cur2=head;
while(cur2&&cur2->next)
{
cur1=cur1->next;
cur2=cur2->next->next;
if(cur1==cur2)
{
ListNode* meet=cur1;
while(head!=meet)
{
head=head->next;
meet=meet->next;
}
return meet;
}
}
return NULL;
}