两个单向链表是否可以合并
发布于: 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 加入
还未添加个人简介











 
    
评论