吴江区建设银行招聘网站,网站开发php有哪些,wordpress调用当着文章tag标签,济南优化专业的公司一#xff0c;相交链表
相交链表#xff08;Leetcode#xff09;
1.1分析
看到这个我们首先想到的就是一个一个比较他们的值有相等的就是交点#xff0c;但是如果a1和b2的值就相等呢#xff1f;所以这个思路不行#xff0c;第二种就是依次比较链表#xff0c;但是这…一相交链表
相交链表Leetcode
1.1分析
看到这个我们首先想到的就是一个一个比较他们的值有相等的就是交点但是如果a1和b2的值就相等呢所以这个思路不行第二种就是依次比较链表但是这个方法也不行因为两个链表长度不行不能这样比较。所以根据第二种的思路我们可以先分别遍历两个链表然后找到长的那个让它先走他们的差值步最后再一起遍历找到他们的交点。
1.2代码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curAheadA;struct ListNode *curBheadB;int lenA1,lenB1;//计算两个链表的长度while(curA-next){curAcurA-next;lenA;}while(curB-next){curBcurB-next;lenB;}//不相交if(curA!curB){return NULL;}//相交int gapabs(lenA-lenB);//找出长的那一个struct ListNode *LonglistheadA;struct ListNode *ShortlistheadB;if(lenAlenB){LonglistheadB;ShortlistheadA;}//长的先走while(gap--){LonglistLonglist-next;}//一起走找出交点while(Longlist!Shortlist){LonglistLonglist-next;ShortlistShortlist-next;}return Longlist;
}二环形链表
环形链表Leetcode
2.1分析
这个题目我们可以用我们之前写过的一道oj题来解那就是快慢指针。 主要思路就是因为是环形链表他会一直的向前走所以快指针循环到一定的程度他就一定会和慢的那个指针相遇。
2.2代码
bool hasCycle(struct ListNode *head) {struct ListNode *fast;struct ListNode *slow;fastslowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){return true;}}return false;
}三环形链表 II
环形链表 IILeetcode
3.1分析
这个题目和上面那个有点不同的是他要求我们返回入环的第一个节点。 我们先来进行数学分析。 然后我们就可直到从头开始走到入口和从快慢指针相遇的地方开始走那么他们相遇的位置就是入口。
3.代码
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow,*fast;slowfasthead;while(fast fast-next){slowslow-next;fastfast-next-next;if(slow fast){struct ListNode *meetslow;while(head!meet){headhead-next;meetmeet-next;}return meet;}}return NULL;
}
