力扣 - 剑指 Offer 52. 两个链表的第一个公共节点
题目
剑指 Offer 52. 两个链表的第一个公共节点
思路1(栈)
- 若两个链表相遇,则从它开始相遇的地方到链表末尾应该都是相同的,那么我们可以将两个链表分别放入两个栈中,然后依次循环比较两个栈顶的节点,同时用
pre
记录上一个节点,直到当前两个栈顶节点不相等,那么pre
节点就是他们开始相遇的地方
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
LinkedList stack1 = new LinkedList<>();
LinkedList stack2 = new LinkedList<>();
// 使用两个栈分别存储两个链表的元素
while (headA != null) {
stack1.push(headA);
headA = headA.next;
}
while (headB != null) {
stack2.push(headB);
headB = headB.next;
}
// 若两个链表存在相同的节点,则两个栈pop出来的节点应该是一样的
// 如果pop出来的不一样,说明上一个pop出来相同节点才是相遇开始的节点
// 因此我们需要pre来记录上一个相同的节点,初始值要为null,如果没有相遇,那么会直接返回null
ListNode pre = null;
while (!stack1.isEmpty() && !stack2.isEmpty()) {
ListNode p1 = stack1.pop();
ListNode p2 = stack2.pop();
if (p1 != p2) {
break;
}
// 如果没有相遇,就不会执行这条语句,因此此时pre为 null,返回的值也是 null
pre = p1;
}
// 返回结果
return pre;
}
}
复杂度分析
- 时间复杂度:\(O(N+M)\)
- 空间复杂度:\(O(N+M)\)
思路2(差值法)
- 先分别计算两个链表的长度记为
lengthA
和lengthB
,得到他们的差值n
,让长的那个链表先走n
步,然后两个链表再一起走,第一个相等的地方,则是链表开始相遇的地方
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA = 0;
int lengthB = 0;
ListNode pA = headA;
ListNode pB = headB;
// 先获取两个链表的长度
while (pA != null) {
pA = pA.next;
lengthA++;
}
while (pB != null) {
pB = pB.next;
lengthB++;
}
// 计算链表长度差n,将长的链表先走n步
int n = lengthA > lengthB ? lengthA - lengthB : lengthB - lengthA;
while (lengthA > lengthB && n > 0) {
headA = headA.next;
n--;
}
while (lengthB > lengthA && n > 0) {
headB = headB.next;
n--;
}
// 然后两个链表才开始同时一起走
// 知道两个节点相等 或者 都为null的时候结束循环
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}
}
复杂度分析
- 时间复杂度:\(O(N+M)\)
- 空间复杂度:\(O(1)\)
思路3(双指针)
- 使用两个指针
pA
和pB
分别指向两个链表,然后同时前进,如果到了链表末尾,就跳到另一条链表的头节点(要保证不会再跳回来,否则导致死循环) - 在这过程中,要判断节点是否相等,第一次相等的地方就是相交的地方,如果没有那就返回
null
- 在
while
中的判断条件要为当前两个节点是否相等,因为不这样的话,如果不存在相交的节点,那么循环就会一直重复下去;如果判断条件为当前两个节点是否相等的话,如果没有相交节点也不会一直循环下去,因为两个指针遍历的长度都为两个链表长度之和,所以最后都会指向null
,此时都为null
相等,跳出循环
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
// 判断是否相等,遇到相同节点,结束循环;如果链表中没有相同节点,那么跳出循环的条件是他们都为 null 的时候
while (pA != pB) {
// 判断的要为当前节点
// 如果判断的是next节点,那么到时候就会导致pA、pB永远不会是null
if (pA == null) {
pA = headB;
} else {
pA = pA.next;
}
if (pB == null) {
pB = headA;
} else {
pB = pB.next;
}
}
return pA;
}
}
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(1)\)
思路4(哈希表)
- 先选择其中一个链表,将其节点全部加入到哈希表中,然后再开始遍历另一个链表,同时也加入到哈希表中
- 如果加入的节点和哈希表冲突了,那么这个节点就是交点
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet set = new HashSet<>();
// 遍历一次,将链表A里的所有节点添加到set中
while (headA != null) {
set.add(headA);
headA = headA.next;
}
// 再遍历一次链表B,同时将链表的节点添加到set中,如果添加失败返回false,那么说明找到相同的那个节点了,直接返回该节点
while (headB != null) {
if (!set.add(headB)) {
return headB;
}
headB = headB.next;
}
// 如果遍历链表B的时候都没有找到,说明不存在相同的节点,就返回 null
return null;
}
}
复杂度分析
- 时间复杂度:\(O(N+M)\)
- 空间复杂度:\(O(N)\),哈希表所占空间大小