LeetCode 面试题 02.07：链表相交

面试题 02.07：链表相交

题目描述

给你两个单链表的头节点 headA 和 headB，请你找出并返回它们相交的起始节点。如果两个链表没有相交，则返回 NULL。

假设链表不包含环，并且相交后的所有节点为公共节点。

---

代码实现

#include <stdio.h>
#include <stdlib.h>// 链表节点定义
struct ListNode {int val;struct ListNode* next;
};// 找到两个链表相交的起始节点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if (!headA || !headB) return NULL;struct ListNode *pA = headA, *pB = headB;while (pA != pB) {  // 当两个指针相遇时，说明找到了相交节点pA = pA ? pA->next : headB;  // 如果 pA 到链表末尾，则切换到 headBpB = pB ? pB->next : headA;  // 如果 pB 到链表末尾，则切换到 headA}return pA;  // 返回相交节点或 NULL
}// 创建链表节点
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 打印链表
void printList(struct ListNode* head) {struct ListNode* current = head;while (current) {printf("%d -> ", current->val);current = current->next;}printf("NULL\n");
}// 主函数测试
int main() {// 创建链表 A：1 -> 2 -> 3 -> 4 -> 5struct ListNode* headA = createNode(1);headA->next = createNode(2);headA->next->next = createNode(3);headA->next->next->next = createNode(4);headA->next->next->next->next = createNode(5);// 创建链表 B：9 -> 4 -> 5struct ListNode* headB = createNode(9);headB->next = headA->next->next->next;  // B 的第二个节点指向 A 的第四个节点printf("链表 A: ");printList(headA);printf("链表 B: ");printList(headB);// 找到相交节点struct ListNode* intersection = getIntersectionNode(headA, headB);if (intersection) {printf("两个链表相交于节点值: %d\n", intersection->val);} else {printf("两个链表不相交\n");}return 0;
}

---

逐行解释代码

1. 链表节点定义

struct ListNode {int val;struct ListNode* next;
};

• 这是链表节点的定义。每个节点包含一个值 val 和一个指向下一个节点的指针 next。

---

2. 找到链表相交节点函数

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if (!headA || !headB) return NULL;

• 如果 headA 或 headB 为 NULL，说明至少有一个链表为空，因此它们不可能相交，直接返回 NULL。

    struct ListNode *pA = headA, *pB = headB;

• 定义两个指针 pA 和 pB，分别指向链表 A 和 B 的头节点。

    while (pA != pB) {  pA = pA ? pA->next : headB;pB = pB ? pB->next : headA;}

• 通过双指针法遍历两个链表：
  • 如果 pA 走到链表 A 的末尾，则跳转到链表 B 的头节点；
  • 如果 pB 走到链表 B 的末尾，则跳转到链表 A 的头节点。
• 当两个指针 pA 和 pB 相等时（即指向相交节点或同时为 NULL），退出循环。

    return pA;

• 返回指针 pA，即两个链表的相交节点。如果两个链表不相交，返回 NULL。

---

3. 创建链表节点

struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}

• 动态创建链表节点，并初始化节点值 val 和指针 next。

---

4. 打印链表

void printList(struct ListNode* head) {struct ListNode* current = head;while (current) {printf("%d -> ", current->val);current = current->next;}printf("NULL\n");
}

• 遍历链表并打印每个节点的值，直到链表末尾。

---

5. 主函数测试

    // 创建链表 A：1 -> 2 -> 3 -> 4 -> 5struct ListNode* headA = createNode(1);headA->next = createNode(2);headA->next->next = createNode(3);headA->next->next->next = createNode(4);headA->next->next->next->next = createNode(5);

• 创建链表 A，其中节点的值分别为 1 -> 2 -> 3 -> 4 -> 5。

    // 创建链表 B：9 -> 4 -> 5struct ListNode* headB = createNode(9);headB->next = headA->next->next->next;  // B 的第二个节点指向 A 的第四个节点

• 创建链表 B，其中节点的值为 9 -> 4 -> 5。注意，链表 B 的第二个节点直接指向链表 A 的第四个节点，模拟了两个链表相交的情况。

    struct ListNode* intersection = getIntersectionNode(headA, headB);if (intersection) {printf("两个链表相交于节点值: %d\n", intersection->val);} else {printf("两个链表不相交\n");}

• 调用 getIntersectionNode 找到两个链表的相交节点。如果返回值不为 NULL，打印相交节点的值；否则打印 “两个链表不相交”。

---

运行结果

对于链表：

链表 A: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
链表 B: 9 -> 4 -> 5 -> NULL

运行结果为：

链表 A: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
链表 B: 9 -> 4 -> 5 -> NULL
两个链表相交于节点值: 4