给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal
- 相交的起始节点的值。如果不存在相交节点,这一值为 0
listA
- 第一个链表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;
}