java 相交鏈表的實現(xiàn)示例

更新時間：2021年11月08日 09:14:59 作者：宗旨飛翔

本文主要介紹了java 相交鏈表的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

1.題目

相交鏈表：給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表沒有交點，返回 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;

然后根據(jù)長度差值的正負判斷誰長，將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("不存在相交結點！");
        }

    }

在這里插入圖片描述