java如何实现相交链表

这篇文章主要为大家展示了“java如何实现相交链表”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“java如何实现相交链表”这篇文章吧。

1.题目

相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。相交链表

2.分析

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

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

长度不同：

长度相同：

首先求长度，先假设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("没有相交结点！");        }    }

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如何实现相交链表”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网行业资讯频道！