剑指 Offer 52. 两个链表的第一个公共节点

摘要

剑指 Offer 52. 两个链表的第一个公共节点

一、双指针解法

使用双指针的方法，可以将空间复杂度降至 O(1)。只有当链表 headA headB都不为空时，两个链表才可能相交。因此首先判断链表 headA和 headB是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA和 headB 都不为空时，创建两个指针pA 和pB，初始时分别指向两个链表的头节点 headA和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

• 每步操作需要同时更新指针 pA 和 pB。
• 如果指针 pA不为空，则将指针 pA移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
• 如果指针 pA 为空，则将指针 pA移到链表headB 的头节点；如果指针 pB为空，则将指针 pB 移到链表 headA的头节点。
• 当指针pA 和pB指向同一个节点或者都为空时，返回它们指向的节点或者 null。

package Linklist;import java.util.HashSet;
import java.util.Set;/*** @Classname JZ52两个链表的第一个公共节点* @Description TODO* @Date 2023/2/11 13:39* @Created by xjl*/
public class JZ52两个链表的第一个公共节点 {public class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}// 采用的是双指针的方式ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA;ListNode pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}// 使用的是双指针来实现ListNode getIntersectionNodecpoy(ListNode headA, ListNode headB) {if (headA==null|| headB==null){return null;}ListNode pA=headA;ListNode pB=headB;while (pA!=pB){pA=pA==null?headB:pA.next;pB=pB==null?headA:pB.next;}return pA;}}

复杂度分析

• 时间复杂度：O(m+n)，其中 m 和 n 是分别是链表headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
• 空间复杂度：O(1)。

 二、哈希集合解法

判断两个链表是否相交，可以使用哈希集合存储链表节点。

• 首先遍历链表 headA，并将链表 headA中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
• 如果当前节点不在哈希集合中，则继续遍历下一个节点；
• 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都是两个链表的公共节点，因此在链表 head 中遍历到的第一个在哈希集合中的节点就是两个链表的第一个公共节点，返回该节点。

如果链表 headB中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。

public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {Set<ListNode> visited = new HashSet<ListNode>();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;} 

复杂度分析

• 时间复杂度是O(m+n), m、n分别是链表headA和headB的长度。需要遍历两个链表的各一次。
• 空间复杂度m,m 是链表 headA的长度。需要使用哈希集合存储链表 headA中的全部节。

博文参考

《Leetcode》