题目:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
题目链接:160.链表相交
题目思路:定义两个指针,分别遍历两链表,如果指针有相同的,则说明有相交的节点
代码示例:
代码逻辑:
- 首先,通过遍历两个链表分别获取它们的长度
lenA
和lenB
,同时记录遍历到的节点为curA
和curB
。 - 接着,比较两个链表的长度,让
curA
指向较长的链表的头节点,curB
指向较短链表的头节点。 - 然后,通过计算长度差
gap
,将两个链表的起点对齐,即让较长链表的指针curA
先向后移动gap
步,使得curA
和curB
处于相同位置。 - 最后,同时遍历
curA
和curB
,当遍历到相同的节点时,即为两个链表的交点,直接返回即可。
这段代码的核心思想是通过先将较长链表的指针先向后移动到与较短链表的起点对齐,然后同时遍历两个链表,找到第一个相同的节点即为交点。
注意!1.我们要比较的是指针相等而非链表中节点的值相等,
2.必须让两条链表比较时的长度是一样的
3.在遍历之前,为了让我们的表达更加清楚,我们可以再次声明让cur指向head,第二次将指针指向头节点的操作是为了确保在开始比较长度之前,两个指针都指向了各自链表的起始位置。这样可以保证在比较链表长度和计算长度差之前,两个指针已经准备好开始遍历链表了。 如果不将指针重新指向头节点,而是直接在计算长度差之后开始遍历链表,那么在确定两个指针的起始位置时就可能出现错误,导致最终的比较结果也会出现偏差。因此,第二次将指针指向头节点是为了确保开始比较长度时,两个指针都从链表的起始位置开始遍历。
4.注意传入的头节点有两个,所以定义的时候要格外注意。