【LeetCode】160. 相交链表
1 题目描述
160. 相交链表要求给定两个单链表的头节点 headA
和 headB
,任务是找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
2 解题思路
为了解决这个问题,我们可以采用以下策略:
- 计算两个链表的长度:首先分别遍历两个链表以获取它们的长度。
- 使较长链表的头指针与较短链表的头指针对齐:如果一个链表比另一个长,我们需要让较长链表的头指针先向前移动长度差步,使得两个链表的指针处于同一位置。
- 同步移动两个指针直至相交:当两个链表的指针位于同一位置时,我们同步移动这两个指针。一旦两个指针相遇,即找到了相交节点。
3 Java 代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
// 求链表A的长度
while (curA != null) {
lenA++;
curA = curA.next;
}
// 求链表B的长度
while (curB != null) {
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头,lenA为其长度
if (lenB > lenA) {
// 交换 lenA 和 lenB
int tmpLen = lenA;
lenA = lenB;
lenB = tmpLen;
// 交换 curA 和 curB
ListNode tmpNode = curA;
curA = curB;
curB = tmpNode;
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上(末尾位置对齐)
while (gap-- > 0) {
curA = curA.next;
}
// 遍历curA 和 curB,遇到相同则直接返回
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
- 时间复杂度: O(L1 + L2),其中 L1 和 L2 分别是链表 A 和链表 B 的长度。我们需要遍历每个链表一次来计算长度,然后再遍历一次以找到相交节点。
- 空间复杂度: O(1),因为我们只使用了几个指针变量。
4 注意事项
- 计算长度:先计算两个链表的长度,以便知道哪个链表更长。
- 对齐起点:让较长的链表先走长度差步,使得两个链表的末尾对齐。
- 同步遍历:然后同步遍历两个链表,直到找到相同的节点或到达链表末尾。
- 返回结果:如果找到相交节点,返回该节点;否则返回
null
。