脚本宝典收集整理的这篇文章主要介绍了力扣 - 剑指 Offer 52. 两个链表的第一个公共节点,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
剑指 Offer 52. 两个链表的第一个公共节点
pre
记录上一个节点,直到当前两个栈顶节点不相等,那么pre
节点就是他们开始相遇的地方public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
LinkedList<ListNode> stack1 = new LinkedList<>();
LinkedList<ListNode> 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;
}
}
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;
}
}
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;
}
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> 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;
}
}
以上是脚本宝典为你收集整理的力扣 - 剑指 Offer 52. 两个链表的第一个公共节点全部内容,希望文章能够帮你解决力扣 - 剑指 Offer 52. 两个链表的第一个公共节点所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。