0160 相交链表

简单 哈希 双指针

算法思路

初见此题，很容易想到：由于链表相交后不会分叉，因此先更新头指针使得两个链表长度相同，然后同时更新两个链表指针（遍历） 寻找是否存在相交阶段，存在则返回节点，否则返回 NULL。此算法时间复杂度 \(O(m+n)\)，空间复杂度 \(O(1)\)。

阅读题解，官方给出了另一解法：哈希。首先遍历一个链表，将其中所有节点加入哈希表中。再遍历另一个链表，同时查询哈希表，如果存在相同元素则返回节点，如果都不存在则返回 NULL。 此算法时间复杂度 \(O(m+n)\)，空间复杂度 \(O(m)\)。

代码实现

方法一：双指针

intersection-of-two-linked-lists.c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int m = 1, n = 1;
    struct ListNode* a = headA;
    struct ListNode* b = headB;
    while (a->next != NULL) {
        a = a->next;
        m++;
    }
    while (b->next != NULL) {
        b = b->next;
        n++;
    }
    a = headA, b = headB;
    while (m > n) {
        a = a->next;
        m--;
    }
    while (n > m) {
        b = b->next;
        n--;
    }
    do {
        if (a == b) {
            return a;
        }
        a = a->next;
        b = b->next;
    } while (a != NULL);
    return NULL;
}

方法二：哈希

intersection-of-two-linked-lists.c

struct HashTable {
    struct ListNode *key;
    UT_hash_handle hh;
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct HashTable *hashTable = NULL;
    struct ListNode *temp = headA;
    while (temp != NULL) {
        struct HashTable *tmp;
        HASH_FIND(hh, hashTable, &temp, sizeof(struct HashTable *), tmp);
        if (tmp == NULL) {
            tmp = malloc(sizeof(struct HashTable));
            tmp->key = temp;
            HASH_ADD(hh, hashTable, key, sizeof(struct HashTable *), tmp);
        }
        temp = temp->next;
    }
    temp = headB;
    while (temp != NULL) {
        struct HashTable *tmp;
        HASH_FIND(hh, hashTable, &temp, sizeof(struct HashTable *), tmp);
        if (tmp != NULL) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

/*
作者：力扣官方题解
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/