有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
答：判断是否合并就看最后一个元素是否一致，如果一致则存在合并。时间复杂度O(m+n),空间复杂度O(1)
伪代码：
LinkedlistM.getElement(Linkedlist.size()-1) == LinkedlistN.getElement(LinkedlistN.size()-1);
看看结果是true还是false。
if m>n diff = m-nelse diff=n-mlistLong.next(diff)while(true){ if(listLong.next() == listShort.next()){ x = listLong.next() break; }}
还未添加个人签名 2018.12.05 加入
还未添加个人简介
京公网安备 11010502039052号京公网安备 11010502039052号京公网安备 11010502039052号
评论