用C语言实现给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点的地址。如果两个链表不存在相交节点，返回 null。 题目数据保证整个链式结构中不存在环 下图中两个链表在节点 c1 处开始相交:

/**
 * 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 *p = headA;
    struct ListNode *q = headB;
    while (p != q) {
        p = (p == NULL) ? headB : p->next;
        q = (q == NULL) ? headA : q->next;
    }
    return p;
}

思路：

两个指针分别从头节点 headA 和 headB 开始遍历，如果其中一个指针到达了链表的结尾，则将其指向另一个链表的头节点。这样两个指针分别遍历了两个链表的长度之和，因此它们一定会在相交节点相遇，或者在遍历完两个链表后都指向 NULL，此时返回 NULL。

相关问题

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

这是一个编程类的问题，我可以回答。这个问题可以使用双指针法来解决。首先分别遍历两个链表，得到它们的长度。然后让较长的链表先走 abs(lenA - lenB) 步，使得两个链表剩余的长度相等。接着，同时遍历两个链表，比较它们的节点是否相同，如果相同则说明找到了相交节点，返回该节点即可。如果遍历完两个链表都没有找到相交节点，则返回 null。

以下是示例代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int lenA = 0, lenB = 0;
struct ListNode *pA = headA, *pB = headB;
while (pA) {
lenA++;
pA = pA->next;
}
while (pB) {
lenB++;
pB = pB->next;
}
pA = headA;
pB = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
pA = pA->next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
pB = pB->next;
}
}
while (pA && pB) {
if (pA == pB) {
return pA;
}
pA = pA->next;
pB = pB->next;
}
return NULL;
}

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

这是一个编程类的问题，我可以回答。这个问题可以使用双指针法来解决。首先遍历两个链表，得到它们的长度。然后让较长的链表的指针先走 abs(lenA - lenB) 步，使得两个链表剩余的长度相等。然后同时遍历两个链表，找到第一个相同的节点即为相交节点。如果没有相交节点，则返回 null。

以下是示例代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);
    ListNode pA = headA, pB = headB;
    int diff = Math.abs(lenA - lenB);
    if (lenA > lenB) {
        while (diff-- > 0) {
            pA = pA.next;
        }
    } else {
        while (diff-- > 0) {
            pB = pB.next;
        }
    }
    while (pA != null && pB != null) {
        if (pA == pB) {
            return pA;
        }
        pA = pA.next;
        pB = pB.next;
    }
    return null;
}

private int getLength(ListNode head) {
    int len = 0;
    ListNode p = head;
    while (p != null) {
        len++;
        p = p.next;
    }
    return len;
}