罗山网站建设,宿迁建设局网站拆除备案,惠州市网站建设企业,太原网站网络推广摘要
剑指 Offer 52. 两个链表的第一个公共节点
一、双指针解法
使用双指针的方法#xff0c;可以将空间复杂度降至 O(1)。只有当链表 headA headB都不为空时#xff0c;两个链表才可能相交。因此首先判断链表 headA和 headB是否为空#xff0c;如果其中至少有一个链表为…摘要
剑指 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 (headAnull|| headBnull){return null;}ListNode pAheadA;ListNode pBheadB;while (pA!pB){pApAnull?headB:pA.next;pBpBnull?headA:pB.next;}return pA;}}复杂度分析
时间复杂度O(mn)其中 m 和 n 是分别是链表headA 和 headB 的长度。两个指针同时遍历两个链表每个指针遍历两个链表各一次。空间复杂度O(1)。二、哈希集合解法
判断两个链表是否相交可以使用哈希集合存储链表节点。
首先遍历链表 headA并将链表 headA中的每个节点加入哈希集合中。然后遍历链表 headB对于遍历到的每个节点判断该节点是否在哈希集合中如果当前节点不在哈希集合中则继续遍历下一个节点如果当前节点在哈希集合中则后面的节点都在哈希集合中即从当前节点开始的所有节点都是两个链表的公共节点因此在链表 head 中遍历到的第一个在哈希集合中的节点就是两个链表的第一个公共节点返回该节点。
如果链表 headB中的所有节点都不在哈希集合中则两个链表不相交返回 null。 public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {SetListNode visited new HashSetListNode();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(mn), m、n分别是链表headA和headB的长度。需要遍历两个链表的各一次。空间复杂度m,m 是链表 headA的长度。需要使用哈希集合存储链表 headA中的全部节。
博文参考
《Leetcode》
