输入两个链表,找出它们的第一个公共节点。
方法一:辅助栈
使用两个栈 $S1$ 和 $S2$ ,分别存储链表 $A$ 和 $B$,一开始将 $A$ 和 $B$ 都存入栈中。使用 ans 指向最终答案。
然后不断弹出,弹出的过程中,判断两个节点是否相等,如果相等则记录下来,$ans$ 指向相等的节点,然后继续弹出直到两个节点不相等,则 $ans$ 指向的节点就是最终答案。
代码:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Deque<ListNode> sA = new LinkedList<>();
Deque<ListNode> sB = new LinkedList<>();
putIntoStack(headA, sA);
putIntoStack(headB, sB);
ListNode ans = null;
// 判断是否有共同节点
boolean intersect = false;
while (!sA.isEmpty() && !sB.isEmpty()) {
ListNode a = sA.pop();
ListNode b = sB.pop();
if (a != b) {
return ans;
}
intersect = true;
ans = a;
}
return intersect ? ans : null;
}
private void putIntoStack(ListNode head, Deque<ListNode> stack) {
while (head != null) {
stack.push(head);
head = head.next;
}
}
复杂度分析
- 时间复杂度$O(MN)$:$M$、$N$ 分别为两个链表的长度。
- 空间复杂度$O(MN)$:辅助栈最多要存储两个链表的所有节点。
方法二:快慢指针
先计算两条链表的长度,然后计算长度差 d,快指针现在先对较长的链表上走 d 步。然后慢指针在快指针走了 d 步后,两条指针同时走。
- 如果快慢指针指向的节点相同,那么它是第一个公共节点;
- 如果快慢指针直到走完都没有相等,那么不存在公共节点。
代码:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 比较两条链表的长度,得出二者的长度差值 d
// 长的那条链表的指针先走 d 步,然后两个链表指针同时走,第一次相等时,就是第一相交节点
int lenA = listLen(headA);
int lenB = listLen(headB);
ListNode smaller, bigger;
smaller = lenA < lenB ? headA : headB;
bigger = smaller == headA ? headB : headA;
int diff = Math.abs(lenA - lenB);
while (diff > 0) {
bigger = bigger.next;
diff--;
}
while (smaller != null && bigger != null) {
if (smaller == bigger) {
return smaller;
}
smaller = smaller.next;
bigger = bigger.next;
}
return null;
}
private int listLen(ListNode head) {
int ans = 0;
while (head != null) {
ans++;
head = head.next;
}
return ans;
}
复杂度分析:
- 时间复杂度$O(MN)$:$M$、$N$ 分别为两个链表的长度。
- 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。
方法三:
假设链表 $A$ 的非公共长度为 $a$,链表 $B$ 的非公共长度为 $b$,二者的公共长度为 $c$。
观察上图,如果先走完链表 $A$ 然后再走链表 $B$ 的 $b$ 部分,可以到达公共点。同样的,如果先走完链表 $B$ 然后再走链表 $A$ 的 $a$ 部分,可以达到公共点。关系如下:
$$
a + c + b = b + c + a
$$
如果两个链表没有公共部分,即 $c = 0$,那么走完两条链表后,会指向 null
。
关系如下:
$$
a + b = b + a
$$
代码:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = a != null ? a.next : headB;
b = b != null ? b.next : headA;
}
return a;
}
复杂度分析
- 时间复杂度$O(MN)$:$M$、$N$ 分别为两条链表的长度。
- 空间复杂度$O(1)$:辅助变量占用常数大小的空间。
评论区