每日一题算法——链表相交

链表相交

力扣题目链接

暴力解法:飘过

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * cur = headA;while(cur != NULL){ListNode* curb = headB;while(curb != NULL){if(curb==cur){return cur;}curb = curb->next;}cur = cur->next;}return NULL;}
};

非暴力解法：

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * cur = headA;ListNode* curb = headB;int counta=0;int countb=0;while(cur != NULL){counta++;cur = cur->next;}while(curb != NULL){countb++;curb = curb->next;}cur = headA;curb = headB;int n = 0;if(counta > countb){n = counta - countb;for(int i =0 ;i<n;i++){cur = cur->next;}}else{n = countb - counta;for(int i =0 ;i<n;i++){curb = curb->next;}}while(cur != NULL && curb !=NULL){if(cur == curb){return cur;}cur = cur->next;curb = curb->next;}return NULL;}
};