leetcode160：相交链表（intersection-of-two-linked-lists）

[carloscn]

问题描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

---

示例一：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

---

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/intersection-of-two-linked-lists

[carloscn]

方法一： 两层循环

嵌套两层循环，第一层锚点，然后在第一层内遍历所有节点，查找是否有相同的节点，接着，第一层的节点指向下一个，然后直至第一层所有的节点都被遍历。最稳妥，但是时间复杂度最高的算法。

//
//           5 -> 7
//                |
//                V
//      1 -> 2 -> 3 -> 4 -> 5 -> NULL
static int32_t find_intersection_in_loop(LINKLIST_T *list1, LINKLIST_T *list2, int64_t *out_val)
{
    int32_t ret = 0;
    LINKLIST_T *list1_current_node = list1;
    LINKLIST_T *list2_current_node = list2;

    UTILS_CHECK_PTR(list1);
    UTILS_CHECK_PTR(list2);
    UTILS_CHECK_PTR(out_val);

    while (list1_current_node->next != NULL) {
        while (list2_current_node->next != NULL) {
            if (list1_current_node == list2_current_node) {
                *out_val = list1_current_node->val;
                goto finish;
            }
            list2_current_node = list2_current_node->next;
        }
        list2_current_node = list2->next;
        list1_current_node = list1_current_node->next;
    }

    LOG("no intersection point.\n");
    *out_val = 0xFFFF;

finish:
    return ret;
}

[carloscn]

方法二：使用hash映射表

遍历第一个链表，把每个节点的地址转换为字符串作为hash key，把value作为相应的映射。然后遍历第二个链表，在hash表中找这个key值。

static int32_t find_intersection_in_hash_map(LINKLIST_T *list1, LINKLIST_T *list2, int64_t *out_val)
{
    int32_t ret = 0;
    size_t count = 0;
    LINKLIST_T *current_node = list1;
    HASH_MAP_T *hash_map = NULL;
    char *hash_key = NULL;
    int64_t val = 0;

    UTILS_CHECK_PTR(list1);
    UTILS_CHECK_PTR(list2);
    UTILS_CHECK_PTR(out_val);

    hash_map = hashmap_malloc(1000);
    UTILS_CHECK_PTR(hash_map);

    while (NULL != current_node) {
        ret = utils_int64_convert_str((int64_t)current_node, &hash_key);
        UTILS_CHECK_RET(ret);

        ret = hashmap_push(hash_map, hash_key, current_node->val);
        UTILS_CHECK_RET(ret);

        current_node = current_node->next;

        free(hash_key);
        hash_key = NULL;
    }

    current_node = list2;
    while (NULL != current_node) {
        ret = utils_int64_convert_str((int64_t)current_node, &hash_key);
        UTILS_CHECK_RET(ret);

        ret = hashmap_get(hash_map, hash_key, &val);
        if (0 == ret) {
            *out_val = val;
            goto finish;
        }

        current_node = current_node->next;

        free(hash_key);
        hash_key = NULL;
    }
    ret = 0;
    LOG("no intersection point.\n");
    *out_val = 0xFFFF;

finish:
    if (NULL != hash_key) {
        free(hash_key);
    }
    hashmap_free(hash_map);
    return ret;
}

[carloscn]

方法三：思维技巧

感谢leetcode朋友的的思路，我也是看了之后才学到。看图就明白了：

不过这个方法有个问题，就是如果两个链表没有相交就会出现无限循环，因此我们需要对这种情况处理一下。设定一个count，两个链表遍历到尾部的时候count++，如果count超过2，那么就说明两个链表没有交点。

static int32_t find_intersection_in_double_pointer(LINKLIST_T *list1, LINKLIST_T *list2, int64_t *out_val)
{
    int32_t ret = 0;
    size_t count = 0;
    LINKLIST_T *list1_current_node = list1;
    LINKLIST_T *list2_current_node = list2;

    UTILS_CHECK_PTR(list1);
    UTILS_CHECK_PTR(list2);
    UTILS_CHECK_PTR(out_val);

    while ((list1_current_node != list2_current_node)) {
        list1_current_node = (NULL != list1_current_node) ? (list1_current_node->next) : (list2);
        list2_current_node = (NULL != list2_current_node) ? (list2_current_node->next) : (list1);

        // anti no intersection linked lists
        if ((NULL == list1_current_node) ||
            (NULL == list2_current_node)) {
            count ++;
            if (count > 2) {
                LOG("no intersection point.\n");
                *out_val = 0xFFFF;
                goto finish;
            }
        }
    }

    *out_val = list1_current_node->val;

finish:
    return ret;
}

[carloscn]

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/linklist/07_intersection-of-two-linked-list_160.c

result: