Solution 7: 判断两链表是否相交

问题描述

RT.

解决思路

(1) 两链表都是单向链表：判断两链表的末尾节点是否相同；

(2) 两链表中一个有环，一个没环：不可能相交；

(3) 两链表都有环：slow-fast双指针方法。

程序

public class ListIntersection {
	// two single list
	public boolean isIntersectionOfTwoSingleList(ListNode l1, ListNode l2) {
		if (l1 == null || l2 == null) {
			return false;
		}

		// whether the end of two list is same
		ListNode endOfList1 = getEndOfList(l1);
		ListNode endOfList2 = getEndOfList(l2);

		return endOfList1 == endOfList2;
	}

	private ListNode getEndOfList(ListNode head) {
		if (head == null) {
			return null;
		}

		ListNode node = head;
		while (node.next != null) {
			node = node.next;
		}
		return node;
	}

	// two list with cycle
	public boolean isIntersectionOfTwoListWithCycle(ListNode l1, ListNode l2) {
		if (l1 == null || l2 == null) {
			return false;
		}

		ListNode slow = l1, fast = l2;

		while (fast.next != null || fast != null || slow != null) {
			slow = slow.next;
			fast = fast.next.next;
			if (slow == fast) {
				return true;
			}
		}

		return false;
	}
}

Follow up

求出两个链表相交的第一个节点（如果存在的话）。

(1) 两条单链表

a. 求出两条链表的长度及长度之差diff，然后设立两个指针指向两链表的头结点，其中指向长链表头结点的指针向前移动diff步；

b. 然后同时移动两指针，直到所指节点相同（地址相同）为止，否则返回null。

(2) 两条链表有环

首先slow-fast，直到相遇为止，其中任意一个指针指回其头结点，然后slow和fast指针同时移动，直到相遇，相遇的节点为第一个相交的节点。

（注意：可能有两个相交的节点）

程序

public class ListIntersection2 {
	// two single list
	public ListNode getFirstIntersectionNodeOfSingleList(ListNode l1,
			ListNode l2) {
		ListNode longNode = l1, shortNode = l2;

		int len1 = getLenOfList(l1);
		int len2 = getLenOfList(l2);

		if (len1 < len2) {
			longNode = l2;
			shortNode = l1;
		}

		int diff = Math.abs(len1 - len2);

		// long move diff steps
		while (diff > 0) {
			longNode = longNode.next;
			--diff;
		}

		while (longNode != null && shortNode != null) {
			if (longNode == shortNode) {
				return longNode;
			}
			longNode = longNode.next;
			shortNode = shortNode.next;
		}

		return null;
	}

	private int getLenOfList(ListNode head) {
		ListNode node = head;
		int len = 0;

		while (node != null) {
			++len;
			node = node.next;
		}

		return len;
	}

	// two list with cycle
	public ListNode getFirstIntersectionNodeOfCycleList(ListNode l1, ListNode l2) {
		if (l1 == null || l2 == null) {
			return null;
		}

		ListNode slow = l1, fast = l2;

		while (fast.next != null || fast != null || slow != null) {
			if (fast == slow) {
				break;
			}
			slow = slow.next;
			fast = fast.next.next;
		}

		if (fast == null || slow == null) {
			return null;
		}

		slow = l1;
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		
		return slow;
	}
}