网站开发的思维导图,宜宾市珙县住房城乡建设网站,南和县住房和建设局网站,wordpress自适应汉化主题方法一#xff1a;双指针法
算法思想#xff1a; 使用两个指针p1#xff0c;p2分别遍历headA和headB。 当p1遍历完headA或p2遍历完headB#xff0c;我们让该指针去遍历另一个链表。 由于两个指针走的路程相同#xff0c;所以若两链表相交#xff0c;则p1#xff0c;p2一…方法一双指针法
算法思想 使用两个指针p1p2分别遍历headA和headB。 当p1遍历完headA或p2遍历完headB我们让该指针去遍历另一个链表。 由于两个指针走的路程相同所以若两链表相交则p1p2一定会在第一个交点处相遇。 若两个链表不相交则p1p2会同时指向空。 代码
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1 headA, *p2 headB;while (p1 ! p2){if (p1 nullptr) p1 headB;else p1 p1-next;if (p2 nullptr) p2 headA;else p2 p2-next;}return p1;}
};方法二对齐法
算法思路 先找到较长的链表并计算两个链表的长度之差dist使长链表先进行遍历走完这个长度之差dist使得两个链表对齐。 而后令短链表和长链表同步开始遍历。 若两链表相交则p1p2一定会在第一个交点处相遇。 若两个链表不相交则p1p2会同时指向空。 代码
class Solution {
public:int getLen(ListNode* head){ListNode* p head;int len 0;while (p ! nullptr){len ;p p-next;}return len;}ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* longList headA, *shortList headB;int len1 getLen(longList), len2 getLen(shortList);int dist len1 - len2;if (dist 0){longList headB;shortList headA;dist len2 - len1;}while (dist --){longList longList-next;}while (longList ! shortList){longList longList-next;shortList shortList-next;}return longList;}
};
