两个单向链表是否可以合并
发布于: 2020 年 07 月 29 日
public Object getMergeElement(Node m,Node n) { // 获取两个链表的最后一个元素 Node tmpm; Node tmpn; Node orgM = m; Node orgN = n; int mLength = 0; int nLength = 0; while(m.nextNode != null) { tmpm = m; m = m.nextNode; mLength++; } while(n.nextNode != null) { tmpn = n; n = n.nextNode; nLength++; } // 如果两个链表的最后一个元素不相等,则两个链表不能合并 if(tmpm.equmls(tmpn)) { return null; } // 如果两个链表最后一个元素相等,则两个链表可以合并 // 找出长度较长的链表,从长度差位置开始寻找合并点 m = orgM; n = orgN; if(mLength > nLength) { for(int i = 0; i < mLength-nLength; i++) { m = m.nextNode; } for(int j = 0; j < nLength; j++) { if(m.equmls(n)) { return m; } m = m.nextNode; n = n.nextNode; } } else { for(int i = 0; i < nLength-mLength; i++) { n = n.nextNode; } for(int j = 0; j < mLength; j++) { if(n.equmls(m)) { return n; } m = m.nextNode; n = n.nextNode; } } }
其时间复杂度为O(n),空间复杂度为O(1)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
划线
评论
复制
发布于: 2020 年 07 月 29 日阅读数: 48
潜默闻雨
关注
还未添加个人签名 2018.11.23 加入
还未添加个人简介
评论