本文共 1346 字，大约阅读时间需要 4 分钟。
在编程过程中，我们有时需要处理单链表数据结构的问题，其中一个常见问题是如何找到两个单链表的起始相交节点。以下是解决这个问题的详细思路和代码实现。
找到两个单链表相交起始节点的关键在于以下几个步骤：
计算链表长度：首先，我们需要计算两个链表的长度。通过遍历每个链表，我们可以确定每个链表的结尾节点的位置。
检查是否相交：如果两个链表的末尾节点不在同一个位置，那么它们显然不相交。此时，我们可以直接返回NULL。
计算长度差值：如果两个链表的末尾节点位置相同，那么它们必定相交。接下来，我们需要计算两个链表的长度差值，并让较长的链表从头开始移动这个差值的位置。这样，两个链表的末尾节点就能对齐。
同时遍历链表：从对齐后的位置开始，同时遍历两个链表，找到第一个相同的节点，这个节点就是两个链表的起始相交节点。
这种方法的核心思想是通过计算链表长度差值来对齐两个链表，然后再同时遍历它们，从而高效地找到相交的起始节点。
以下是基于上述思路的代码实现：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int lenA = 0, lenB = 0; struct ListNode* curA = headA; struct ListNode* curB = headB; // 计算两个链表的长度 while (curA) { curA = curA->next; lenA++; } while (curB) { curB = curB->next; lenB++; } // 检查是否相交的条件 if (curA != curB) { return NULL; } // 计算长度差值 int n = abs(lenA - lenB); curA = headA; curB = headB; // 对齐两个链表 while (n--) { if (lenA > lenB) { curA = curA->next; } if (lenA < lenB) { curB = curB->next; } } // 同时遍历，找到第一个相交节点 while (curA != curB) { curA = curA->next; curB = curB->next; } return curA;} 通过上述方法，我们可以高效地找到两个单链表的起始相交节点。这种方法的时间复杂度为 O(n)，其中 n 是两个链表的总长度。这种复杂度在大多数实际应用中都是可以接受的。
转载地址：http://ncno.baihongyu.com/