欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java 相交链表的实现示例

程序员文章站 2022-03-24 10:27:53
目录1.题目2.分析3.完整代码1.题目相交链表:给你两个单链表的头节点 heada 和 headb ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。相交链表2.分析...

1.题目

相交链表:给你两个单链表的头节点 heada 和 headb ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。相交链表

2.分析

相交链表是y字型next域相同。
定义两个引用pl和ps

java 相交链表的实现示例

如果每个链表相交结点前长度相同,一步一步走,直到相同就找到了相交结点。如果长度不一样,首先要长链表先走差值步,然后再一人走一步直到相遇

长度不同:

java 相交链表的实现示例

java 相交链表的实现示例

长度相同:

java 相交链表的实现示例

java 相交链表的实现示例

java 相交链表的实现示例

首先求长度,先假设pl指向heada:

 listnode pl = heada;
        listnode ps = headb;

        int lena = 0;
        int lenb = 0;
        while (pl != null) {
            lena++;
            pl = pl.next;
        }
        //pl==null;
        pl = heada;

        while (ps != null) {
            lenb++;
            ps = ps.next;
        }
        //ps==null;
        ps = headb;

然后根据长度差值的正负判断谁长,将pl指向长的链表:

int len = lena - lenb;//差值步
        if (len < 0) {
            pl = headb;
            ps = heada;
            len = lenb - lena;
        }

然后长的先走长度差值步,最后一人一步走:

 //pl走差值len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        //同时走,直到相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
        }

3.完整代码

//判断链表相交
    public static listnode getintersectionnode(listnode heada, listnode headb) {
        if (heada == null || headb == null) {
            return null;
        }

        listnode pl = heada;
        listnode ps = headb;

        int lena = 0;
        int lenb = 0;
        while (pl != null) {
            lena++;
            pl = pl.next;
        }
        //pl==null;
        pl = heada;

        while (ps != null) {
            lenb++;
            ps = ps.next;
        }
        //ps==null;
        ps = headb;

        int len = lena - lenb;//差值步
        if (len < 0) {
            pl = headb;
            ps = heada;
            len = lenb - lena;
        }
        //1、pl永远指向最长的链表  ps永远指向最短的链表   2、求到了差值len步

        //pl走差值len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        //同时走,直到相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }

测试:

 public static void main(string[] args) {
        mylinkedlist mylinkedlist = new mylinkedlist();
        mylinkedlist.addlast(12);
        mylinkedlist.addlast(23);
        mylinkedlist.addlast(34);
        mylinkedlist.addlast(45);
        system.out.println("mylinkedlist:");
        mylinkedlist.display();

        mylinkedlist mylinkedlist1 = new mylinkedlist();
        mylinkedlist1.addlast(13);
        mylinkedlist1.addlast(22);
        mylinkedlist1.addlast(30);
        system.out.println("mylinkedlist1:");
        mylinkedlist1.display();
        createcut(mylinkedlist.head, mylinkedlist1.head);
        try {
            listnode ret = getintersectionnode(mylinkedlist.head, mylinkedlist1.head);
            mylinkedlist.display2(ret);
        } catch (nullpointerexception e) {
            e.printstacktrace();
            system.out.println("没有相交结点!");
        }

    }

java 相交链表的实现示例

mylinkedlist mylinkedlist = new mylinkedlist();
        mylinkedlist.addlast(12);
        mylinkedlist.addlast(23);
        mylinkedlist.addlast(34);
        mylinkedlist.addlast(56);
        system.out.println("mylinkedlist:");
        mylinkedlist.display();

        mylinkedlist mylinkedlist1 = new mylinkedlist();
        mylinkedlist1.addlast(12);
        mylinkedlist1.addlast(23);
        mylinkedlist1.addlast(30);
        system.out.println("mylinkedlist1:");
        mylinkedlist1.display();
        //createcut(mylinkedlist.head,mylinkedlist1.head);
        try {
            listnode ret = getintersectionnode(mylinkedlist.head, mylinkedlist1.head);
            system.out.println(ret.val);
        }catch (nullpointerexception e){
            e.printstacktrace();
            system.out.println("不存在相交结点!");
        }

    }

java 相交链表的实现示例

到此这篇关于java 相交链表的实现示例的文章就介绍到这了,更多相关java 相交链表内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!

相关标签: java 相交链表