C语言面试题之相交链表

相交链表

实例要求

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

实例分析

可以使用两种方法：哈希表方法和双指针方法。
哈希表方法较为直接，但需要额外的空间来存储访问过的节点。
双指针方法是一个空间复杂度为 O(1) 的解法，时间复杂度为 O(N+M)，其中 N 和 M 是两个链表的长度。
基本思路：
1、创建两个指针分别指向两个链表的头节点，然后同时遍历链表。
2、当到达链表末尾时，将指针重定向到另一个链表的头节点。
3、如果两个链表相交，那么这两个指针最终将会在相交点相遇。
4、如果不相交，那么这两个指针将同时到达链表的尾部（都是 NULL）。

示例代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) return NULL;
    
    struct ListNode *ptrA = headA;
    struct ListNode *ptrB = headB;

    // 当两个指针不相遇时，继续遍历
    while (ptrA != ptrB) {
        // 指向下一个节点，如果到达末尾，则指向另一个链表的头节点
        ptrA = (ptrA == NULL) ? headB : ptrA->next;
        ptrB = (ptrB == NULL) ? headA : ptrB->next;
    }

    // 返回相交节点，如果不相交，最终返回 NULL
    return ptrA;
    
}