160. 相交链表
题目链接：160. 相交链表
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：
思路一：
如果两个链表相交，则必有公共结点，我们只需要返回第一个公共结点就可以了，第一个公共结点就是第一个相交结点。怎么找他的第一个公共结点呢？最简单的就是两个循环，去遍历两个链表。用链表B中的结点挨个与链表A的结点比较是否相等。如果存在相等的结点，第一个相等的结点就是两个单链表相交的起始节点，返回任意一个结点。如果没有相交结点，那么两个链表不相交，返回 NULL 。此方法时间复杂度为O(n^2).
代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { for(struct ListNode*i=headA;i!=NULL;i=i->next) { for(struct ListNode*j=headB;j!=NULL;j=j->next) { if(i==j) { return i; } } } return NULL; }
思路二：
如果让两个指针能从下面的地方开始走，那么两个指针相遇的时候一定就是两个单链表相交的起始节点。
那么问题就是怎么找到这两个位置。其实不难发现只要让 curB 先走，让 curB 之后的链表节点数与 curA 后面的节点数一样。只要让长的链表先走 长链表比短链表多的节点数的 步数，就可以了。
代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode*listA=headA; struct ListNode*listB=headB; int countA=0; //A链表的长度 int countB=0; //B链表的长度 //计算B链表的长度 while(listA) { countA++; listA=listA->next; } //计算A链表的长度 while(listB) { countB++; listB=listB->next; } //计算长度差 int n=abs(countA-countB); //先假设A为长链表，B为短炼表 struct ListNode*longlist=headA; struct ListNode*shortlist=headB; //如果不符合就纠正一下 if(countB>countA) { longlist=headB; shortlist=headA; } //让长链表先走 while(n--) { longlist=longlist->next; } //长短链表同时走 while(longlist&&shortlist) { //第一次相遇就是相交的第一个结点 if(longlist==shortlist) { return longlist; } longlist=longlist->next; shortlist=shortlist->next; } return NULL; }
142. 环形链表 II
题目链接：142. 环形链表 II
题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
思路一：
利用带环链表的特点加上严格的逻辑推导：
代码：
struct ListNode *detectCycle(struct ListNode *head){ struct ListNode*frist=head;//快指针 struct ListNode*slow=head;//慢指针 //如果遇到结点为空，就说明不是带环结点，直接返回NULL while(frist&&frist->next) { frist=frist->next->next; //快指针一次走两步 slow=slow->next; //慢指针一次走一步 if(frist==slow)//在环中相遇 { struct ListNode*meet=frist;//一个从环中走 struct ListNode*cur=head;//一个从链表头走 while(meet!=cur)//相遇是循环结束 { meet=meet->next; cur=cur->next; } return meet;//相遇的结点就是环入口点 } } return NULL; }
思路二：
利用快慢指针，让两指针在环中相遇点，将相遇点拆开。相遇点的后一个结点变成新的头节点，相遇点的next指向NULL。这样带环问题就变成了，两个链表相交的问题。
产生的两条新的链表，head 和 phead ，两条链表相交的第一个的以公共结点就是，以前带环链表的环入口处。
代码：
//找到链表相交的第一个结点 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode*listA=headA; struct ListNode*listB=headB; int countA=0; int countB=0; while(listA) { countA++; listA=listA->next; } while(listB) { countB++; listB=listB->next; } int n=abs(countA-countB); struct ListNode*longlist=headA; struct ListNode*shortlist=headB; if(countB>countA) { longlist=headB; shortlist=headA; } while(n--) { longlist=longlist->next; } while(longlist&&shortlist) { if(longlist==shortlist) { return longlist; } longlist=longlist->next; shortlist=shortlist->next; } return NULL; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode*frist=head; struct ListNode*slow=head; while(frist&&frist->next) { frist=frist->next->next; slow=slow->next; //快慢指针在环中相遇 if(frist==slow) { //拆分环行链表段 struct ListNode*phead=frist->next; slow->next=NULL; //返回相交结点 return getIntersectionNode(phead,head); } } return NULL; }
最后：成为自己想成为的样子,才能得到自己想得到的东西。
