第 8 周作业

关注

发布于: 2020 年 12 月 13 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用代码（或伪代码）描述算法，并给出时间复杂度。

基本思路：先求出两个链表的长度，如果存在合并元素，则从后从往前的一定数量的结点是重复的，因此可以以短的链表长度作为长度判断是否存在合并。

时间复杂度 O(m+n)，代码如下：

定义链表

public class LinkNode {	public Object data;	public LinkNode next;
	public LinkNode(Object data) {		this.data = data;	}}

复制代码

查找合并结点

private static LinkNode findFirstMergedNode(LinkNode a, LinkNode d) {		// compute length		int length1 = 0, length2 = 0;		LinkNode tempNode = a;		while (tempNode.next != null) {			length1++;			tempNode = tempNode.next;		}		tempNode = d;		while (tempNode.next != null) {			length2++;			tempNode = tempNode.next;		}
		LinkNode tempa = a;		LinkNode tempd = d;
		// skip nodes		int sub = length1 - length2;		if (sub > 0) {			for (int i = 0; i < sub; i++) {				tempa = tempa.next;			}		} else if (sub < 0) {			for (int i = sub; i < 0; i++) {				tempd = tempd.next;			}		}
		// find the first merged node		while (tempa != tempd) {			tempa = tempa.next;			tempd = tempd.next;		}				return tempa;	}

复制代码

定义数据，调用查找方法，输出结果

public class Main {
	public static void main(String[] args) {
		// init nodes		LinkNode a = new LinkNode("a");		LinkNode b = new LinkNode("b");		LinkNode d = new LinkNode("d");		LinkNode e = new LinkNode("e");		LinkNode f = new LinkNode("f");		LinkNode x = new LinkNode("x");		LinkNode y = new LinkNode("y");		LinkNode z = new LinkNode("z");
		a.next = b;		b.next = x;
		d.next = e;		e.next = f;		f.next = x;
		x.next = y;		y.next = z;
		LinkNode mergedNode =  findFirstMergedNode(a, d);		if (mergedNode != null) {			System.out.println("found the first merged node:" + mergedNode.data);		}		else {			System.out.println("cannot find the first merged node.");		}			}
}

复制代码

发布于: 2020 年 12 月 13 日阅读数: 23

Steven

关注

还未添加个人签名 2008.07.18 加入

还未添加个人简介

发布

暂无评论

创作场景

第 8 周作业

Steven

评论