3.6 判断两个无环链表是否相交 找出相交的第一个结点

本文主要是介绍3.6 判断两个无环链表是否相交 找出相交的第一个结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 前言

本文的一些图片, 资料 截取自编程之美

2. 问题描述

3. 问题分析

这两个问题也是非常经典的问题

对于第一个问题 :
解法一 : 穷举, 穷举两个链表的各个元素, 判断有没有相同的结点

解法二 : 遍历一次较长的链表, 然后将其唯一标识存在一个容器ids中, 然后在遍历一次另一个链表, 查找第二个链表中的元素是否存在于ids中, 如果存在, 则说明存在交点

解法三 : 将一个链表连接到另一个链表中, 然后判断这个合并的大链表中是否存在环, 如果存在环, 则说明存在交点

解法四 : 遍历一次两个链表, 获取每一个链表的最后一个结点, 如果他们最后一个结点相同, 则说明存在交点, 因为如果存在交点, 则这两个链表交点以及该交点之后的数据一定是完全一致的

对于第二个问题 :
解法一 : 穷举, 这个就不说了, 和上面的第一个问题的解法一基本一致, 只不过重点不一样, 这里在于获取第一个重复的结点

解法二 : 利用两个栈维护两个链表的遍历顺序, 然后在开始同时pop, 找到第一个不相同的结点, 第一个不相同的结点之前的哪一个结点即为所求

解法三 : 遍历一次两个链表, 分别获取两个链表的长度arrLen01, arrLen02, 然后较长的链表先走 |arrLen01 - arrLen02| 步, 然后在两个一起走, 比较一起走的时候的两个结点, 找到第一个相同的结点即为所求

4. 代码

备注 : 这里的List为上一节中的LinkedList数据结构, 包括Node, 需要运行的话, 需要复制上一节的相关代码

/*** file name : Test07IfListCross.java* created at : 11:07:45 AM May 28, 2015* created by 970655147*/package com.hx.test04;public class Test07IfListCross {// 1. 判断两个List是否相交// 2. 找到两个链表的第一个相交的结点public static void main(String []args) {LinkedList ll = new LinkedList();LinkedList ll02 = new LinkedList();ll.add(3);ll.add(5);ll.add(6);ll.add(7);ll02.add(3);ll02.add(7);Node node = new Node(3, null);ll.addNode(node);ll02.addNode(node);ll.add(34);ll.add(22);Log.log(ll);Log.log(ll02);ifListCorss01(ll.head, ll02.head);ifListCorss02(ll.head, ll02.head);ifListCorss03(ll.head, ll02.head);ifListCorss04(ll.head, ll02.head);findFirstCrossNode01(ll.head, ll02.head);findFirstCrossNode02(ll.head, ll02.head);findFirstCrossNode03(ll.head, ll02.head);}// 思路 : 穷举 // 遍历head01, head02 如果两个中存在一个结点的next指针 ==  则说明存在交叉结点public static void ifListCorss01(Node head01, Node head02) {Node ls01 = head01, ls02 = head02;bigLoop:while((ls01 = ls01.next) != null) {ls02 = head02;while((ls02 = ls02.next) != null) {if((ls01.next != null) && (ls02 != null) ) {if(ls01 == ls02) {Log.log("exist cross...");break bigLoop;}}}}}// 思路 : 遍历head01  并计算其所有数据的next的hash  然后存入HashSet中 , 之后遍历head02  只要在第二个链表的数据中判断是否存在相同的hash  既可以判断是否存在交叉// 这里使用BloomFilter准确度, 空间使用率会更高, 不能使用BloomFilter, 因为其对于判定数据存在容器中不能打到100%准确public static void ifListCorss02(Node head01, Node head02) {Node[] heads = new Node[]{head02 };Set<Integer> hashes = new HashSet<Integer>();// 遍历head01 将所有数据的next结点的hash计算出来 存入hashSet中Node tmp = head01;while((tmp = tmp.next) != null) {if(tmp.next != null) {Integer hash = hash(tmp.next.toString());hashes.add(hash);}}// 遍历head02  判断是否存在结点的hash存在于之前的hashSetfor(int i=0; i<heads.length; i++) {Node head = heads[i];while((head = head.next) != null) {if(head.next != null) {Integer hash = hash(head.next.toString());if(hashes.contains(hash) ) {Log.log("exist cross...");break ;} else {hashes.add(hash);}}}}}// 将head02 添加到head01后面  在判断 整个大连表是否有环public static void ifListCorss03(Node head01, Node head02) {Node head = head01;while(head.next != null) {head = head.next;}head.next = head02;if(isExistLoop(head01) ) {Log.log("exist cross...");}// 断掉 两个链表的连接head.next = null;}// 只需要判断head01链表 和head02链表中的最后一个结点是否相同  既可以判断两个链表是否存在交叉// 因为这里 给出的是无环链表public static void ifListCorss04(Node head01, Node head02) {Node[] heads = new Node[] {head01, head02 };Node[] tail = new Node[2];for(int i=0; i<heads.length; i++) {Node head = heads[i];while(head.next != null) {head = head.next;}tail[i] = head;}if(tail[0] == tail[1]) {Log.log("exist cross...");}}// 穷举public static void findFirstCrossNode01(Node head, Node head2) {
//      ifListCorss01(head, head2);}// 利用两个个栈维护两个链表的遍历的反顺序// 找到栈中第一个不相同的结点的下一个结点public static void findFirstCrossNode02(Node head, Node head2) {java.util.LinkedList<Node>[] deque = new java.util.LinkedList[2];for(int i=0; i<deque.length; i++) {deque[i] = new java.util.LinkedList<>();}Node[] heads = new Node[] {head, head2 };int[] lengths = new int[2];for(int i=0; i<heads.length; i++) {Node tmp = heads[i];while(tmp.next != null) {tmp = tmp.next;deque[i].push(tmp);lengths[i] ++;}}Node lastOne = null;int shorter = getMinIdx(lengths);while(deque[shorter].size() > 0) {Node tmp = deque[0].pop();if(tmp != deque[1].pop()) {Log.log(lastOne);break;} else {lastOne = tmp;}}}// 维护两个索引, 较长的链表索引   先移动deltaLength步, 然后两个索引同时移动  获取第一个相同的结点public static void findFirstCrossNode03(Node head, Node head2) {Node[] heads = new Node[] {head, head2 };int[] lengths = new int[2];Node tmp = null;for(int i=0; i<heads.length; i++) {tmp = heads[i];while(tmp.next != null) {tmp = tmp.next;lengths[i] ++;}}Node tmpH00 = heads[0], tmpH01 = heads[1];if(lengths[0] > lengths[1]) {for(int i=0; i<lengths[0]-lengths[1]; i++) {tmpH00 = tmpH00.next;}} else {for(int i=0; i<lengths[1]-lengths[0]; i++) {tmpH01 = tmpH01.next;}}while(tmpH00 != null) {if(tmpH00 == tmpH01) {Log.log(tmpH00);break;}tmpH00 = tmpH00.next;tmpH01 = tmpH01.next;}}// 获取lengths中较小的值的索引private static int getMinIdx(int[] lengths) {if(lengths[0] > lengths[1]) {return 1;} else {return 0;}}// 判断一个List中是否存在环private static boolean isExistLoop(Node head) {Set<Integer> hashes = new HashSet<Integer>();while((head = head.next) != null) {if(head.next != null) {Integer hash = hash(head.next.toString());if(hashes.contains(hash) ) {return true;} else {hashes.add(hash);}}}return false;}// 字符串的计算hash的方法private static int hash(String str) {int h = 0;if (h == 0 && str.length() > 0) {char val[] = str.toCharArray();for (int i = 0; i < val.length; i++) {h = 31 * h + val[i];}}return h;}}

5. 运行结果

6. 总结

对于第一个问题的后两种解法, 以及第二个问题的后两种解法, 都是比较经典的, 非常有必要了解一下

注 : 因为作者的水平有限，必然可能出现一些bug, 所以请大家指出！

这篇关于3.6 判断两个无环链表是否相交 找出相交的第一个结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---