判断两个链表是否相交

题目 ：

 

给出两个链表的头指针，比如h1，h2，判断这两个链表是否相交。

 

扩展：

(1) 如果链表可能有环呢？
(2) 如何求出两个相交链表的相交的第一个节点。

 

 

如果链表没有环

 

假设两个链表没有环，如果它们相交，那么它们的最后一个元素必定相同。

 

public boolean isConNLoop(ListNode h1, ListNode h2) {
	if (h1 == null || h2 == null)
		return false;
	ListNode n1 = h1;
	ListNode n2 = h2;
	while (n1.next != null)
		n1 = n1.next;
	while (n2.next != null)
		n2 = n2.next;
	
	if (n1 == n2)
		return true;
	return false;
}

 

它们的交点为

 

public ListNode findPointNLoop(ListNode h1, ListNode h2) {
	if (h1 == null || h2 == null)
		return null;
	ListNode n1 = h1;
	ListNode n2 = h2;
	int len1 = 0;
	int len2 = 0;
	while (n1 != null) {
		n1 = n1.next;
		len1++;
	}
	while (n2 != null) {
		n2 = n2.next;
		len2++;
	}
	
	n1 = h1;
	n2 = h2;
	if (len1 < len2) {
		n1 = h2;
		n2 = h1;
	}
		
	for (int i = len1-len2; i > 0; i--)
		n1 = n1.next;
	
	while (n1 != null && n1 != n2) {
		n1 = n1.next;
		n2 = n2.next;
	}
	return n1;		
}

 

 

如果链表有环

 

如果链表有环且相交，那么这两个链表都是有环的。

找到第一个链表的环点，然后将环断开（当然不要忘记了保存它的下一个节点），然后再来遍历第二个链表，如果发现第二个链表从有环变成了无环，那么他们就是相交的嘛，否则就是不相交的了。

 

public boolean isConLoop(ListNode h1, ListNode h2) {
	ListNode temp = loopEntry(h1);
	ListNode org = temp.next;
	temp.next = null;
	if (isLoop(h2)) {
		temp.next = org;
		return false;
	} else {
		temp.next = org;
		return true;
	}
}

public ListNode loopEntry(ListNode head) {
	if (head == null)
		return null;
	ListNode slow = head;
	ListNode fast = slow.next;
	while (fast != null && fast.next != null && fast != slow) {
		slow = slow.next;
		fast = fast.next.next;
	}
	if (fast == slow) {
		fast = head;
		slow = slow.next;
		while (fast != slow) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}
	return null;
}

 

寻找环点的方法如下：

两个指针，一个走一步，一个走两步，在环中相遇位置为X。然后从头节点和X位置，分别一步一步的走，每次判断是否相遇，相遇点就是所求节点。

证明如下：假设头节点位置为A，环点为M，相遇节点为X，环长为Len。
因为快节点每次比慢节点快一步，慢节点进入环后快节点不用一圈就能赶上慢节点了。
    慢节点走的路程 = AM + MX
    快节点走的路程 = AM + MX  + n * Len
    => 2*(AM + MX ) = AM + MX + n *Len
    => AM + MX = n*Len
    => AM = (n-1)*Len + XM，说明从A到M的距离与X到M的距离，模环长同余。因此分别从A和X走，必然相交于M节点。

 

当两个有环的链表相交时，有以下两种情况：

 

 

在这种情况下，两个链表的交点在环点之前，可以将环点切断，这样就变成了两个无环的链表求相交点。可使用以上方法。

另一种情况为：

 

 

在这种情况下，不存在所谓的相交点。

评论

1 楼 chriszeng87 2011-10-03  

最后第二种情况右下角的那个点是不是可以看作相交点的?上面的那种方法(找到第一个链表的环点，把环切断，然后判断第二个链表是不是环)感觉也可以用的