输入两个链表，找出他们的第一个公共结点输入两个链表，找出他们的第一个公共结点

53 阅读 0 评论 35 点赞

我是靠谱客的博主善良保温杯，最近开发中收集的这篇文章主要介绍输入两个链表，找出他们的第一个公共结点输入两个链表，找出他们的第一个公共结点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

输入两个链表，找出他们的第一个公共结点

解题思路：

此处类名我用汉字，主要为了自己练习，为了后期好找到进行回顾。最要用标准的英文类名呦

/*
  题：输入两个链表，找出他们的第一个公共结点

  重点审题：这种题只知道有两个链表，并不知道链表的长度
 */
public class 链表第一个公共结点 {
    class Node{
        Integer value;
        Node next = null;
        public Node(Integer value){
            this.value = value;
        }
    }
    //链表的头结点
    public Node nn = new Node(null);
    public Node n = nn;
    public void add(Integer num){
        n.next = new Node(num);
        n = n.next;
    }

        //第一种方法：直接遍历两个链表找到相同的结点，采用两层循环，时间复杂度为O（n²），时间复杂度太高
    //第二种方法：单独变量里两个链表，算出链表的长度，A为两个链表长度的差值，让链表长度长的先走A步，然后两个链表一块走
     //            这样时间复杂度为O（n）
    public static Integer find(Node a,Node b){
        //求两个链表的长度
          int lengtha = 0;
          int lengthb = 0;
          Node aa = a;
          Node bb = b;
          while (a.next!=null){
              lengtha++;
              a = a.next;
          }
        while (b.next!=null){
            lengthb++;
            b = b.next;
        }
       // System.out.println(lengtha+"  "+lengthb);
       Integer max = Math.max(lengtha,lengthb);
        for(int i=1;i<=max;i++){
            //让最长链表先走Math.abs(lengtha-lengthb)步
           if(i<=(Math.abs(lengtha-lengthb))){
               if(max==lengtha){
                   aa = aa.next;
               }else{
                   bb = bb.next;
               }
               continue;
           }
           //差值步数走完后，让两个链表一块走，直到有相同的结点值时输出
           aa = aa.next;
           bb = bb.next;
           if(aa.value==bb.value){
               System.out.println("在最长链表的第 "+i+" 结点为第一个公共结点");
               System.out.println("在最短链表的第 "+(i-Math.abs(lengtha-lengthb))+" 结点为第一个公共结点");
               return aa.value;
           }
        }
        return null;
        }

    public static void main(String[] args) {
        //现在有两个链表 a 和 b；第一个公结点为7
        //但是我们事先并不知道链表里的值和长度，这两个链表只是测试用例
        链表第一个公共结点 a = new 链表第一个公共结点();
        Node aa = a.nn;
        a.add(10);
        a.add(30);
        a.add(6);
        a.add(2);

        链表第一个公共结点 b = new 链表第一个公共结点();
        Node bb = b.nn;
        b.add(5);
        b.add(8);
        b.add(9);
        b.add(6);
        b.add(2);

        System.out.println("第一个公共结点的值为："+find(aa,bb));
    }
}