[数据结构与算法] JZ52：两个链表的第一个公共结点

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> JZ52：两个链表的第一个公共结点 -> 正文阅读

[数据结构与算法]JZ52：两个链表的第一个公共结点

题目链接：JZ52：两个链表的第一个公共结点
题目描述：
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
数据范围： n $\le$ 1000
要求：空间复杂度 $O (1)$ ，时间复杂度 $O (n)$
题目分析：
① 根据两个链表的长度差，让链表长的一方先走双方的差值步，之后再一起走！两个结点相同，即为两个链表的第一个公共结点。
时间复杂度O(m+n) 需要遍历两个链表
空间复杂度O(1) 没有借助额外的内存空间
在这里插入图片描述

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       //统计两个链表各自的长度
        int len1 = length(pHead1);
        int len2 = length(pHead2);
        //如果两个链表长度不一，让链表长的一方走两者差值步
        while(len1!=len2){
            if(len1>len2){
                pHead1 = pHead1.next;
                len1--;
            }else{
                pHead2 = pHead2.next;
                len2--;
            }
        }
        //如果两个链表结点相同，则为第一个公共结点
        while(pHead1!=pHead2){
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        //返回pHead1 或者 pHead2 任意一个即可！
        return pHead1;
    }
   
    //统计两个链表的长度
    public int length(ListNode node){
        int count = 0;
        while(node!=null){
            count++;
            node = node.next;
        }
        return count;
    }
}

② 双指针法：循环往前走！pHead1 和 pHead2 一定会在相同位置同时出发！它们就会相遇到一点，即第一个公共结点。
时间复杂度O(m+n) 遍历有限次链表
空间复杂度O(1)
在这里插入图片描述

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode a = pHead1;
        ListNode b = pHead2;
        while(a!=b){
            //a如果为null;就让a指向pHead1重新开始遍历链表
            a=(a==null)?pHead1:a.next;
            b=(b==null)?pHead2:b.next;
        }
        return a;
    }
}

③Set集合去重，遇到第一个重复的元素就是公共元素。
时间复杂度O(m+n), 空间复杂度O(m),需要额外存储Set集合空间pHead1链表的大小m

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> set = new HashSet<>();
        while(pHead1!=null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2!=null){
            if(set.contains(pHead2)){
                return pHead2;
            }
            set.add(pHead2);
            pHead2 = pHead2.next;
        }
        return null;
    }
}