image-20241105131548481

哈希

手感来了,自己用哈希写了一个,记录一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct hashTable{
    struct ListNode* key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(struct ListNode* ikey){
    struct hashTable* tmp;
    HASH_FIND_PTR(hashtable,&ikey,tmp);
    return tmp;
}

void insert(struct ListNode*ikey,int ival){
    struct hashTable* it=find(ikey);
    if(it==NULL){
        struct hashTable* tmp=malloc(sizeof(struct hashTable));
        tmp->key=ikey;
        tmp->val=ival;
        HASH_ADD_PTR(hashtable,key,tmp);
    }
    else{
        it->val=ival;
    }
}


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* aline=headA;
    struct ListNode* bline=headB;
    while(aline!=NULL){
        insert(aline,aline->val);
        aline=aline->next;
    }
    while(bline!=NULL){
        if(find(bline)){
            return bline;
        }
        bline=bline->next;
    }
    return NULL;
}

image-20241105131649089

思路

高手的思路:对不起，相交链表，我做的有点不浪漫。

思路1:

1
两个相交链表a,b,假设a更长,那么求出a-b的长度,让a向后指a-b位,就能把a,b的尾部对齐,之后一步一步走就能走到交点
image-20241105132704149

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int lenA=0,lenB=0;
    while(curA){
        curA=curA->next;
        lenA++;
    }
    while(curB){
        curB=curB->next;
        lenB++;
    }
    curA=headA;
    curB=headB;
    if (lenB > lenA) {
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;

            struct ListNode* tmpNode = curA;
            curA = curB;
            curB = tmpNode;
    }
    int gap=lenA-lenB;
    for(int i=0;i<gap;i++){
        curA=curA->next;
    }
    while(curA){
        if(curA==curB){
            return curA;
        }
        curA=curA->next; 
        curB=curB->next;
    }
    return NULL;

}

image-20241105134407622

思路2:

题解代码:厉害的代码总是离不开数学,这是对这道题一个浪漫的评论:

1
2
3
错的人就算走过了对方的路也还是会错过。

走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

长度有差别,让指针pa和pb走完A和B就可以消除长度差:

image-20241105140823325

如果有交点,那么这样走过一遍后,两者一定会到交点,否则两者都会=NULL,依次题解

代码:

1
2
3
4
5
6
7
8
9
10
11
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL){
        return NULL;
    }
    struct ListNode* pA=headA,*pB=headB;
    while(pA!=pB){
        pA=pA==NULL?headB:pA->next;
        pB=pB==NULL?headA:pB->next;
    }
    return pA;
}