面试题 02.07 链表相交

Posted on | In
Words count in article: 978 | Reading time ≈ 4

题目

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例1：

1
2
3
4
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例2：

1
2
3
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例3：

1
2
3
4
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

提示：

  • 如果两个链表没有交点，返回 null 。
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解法

解法一：

借助HashSet

遍历其中某一个链表，全放入HashSet中。然后遍历剩下一个链表，第一个在HashSet中出现的链表节点就是交点。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
	 * 借助HashSet
	 * @param headA
	 * @param headB
	 * @return
	 */
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		HashSet<ListNode> set = new HashSet<>();
		while (null != headA) {
			set.add(headA);
			headA = headA.next;
		}
		
		while (null != headB) {
			if (set.contains(headB)) {
				return headB;
			}
			headB = headB.next;
		}
		return null;
	}

解法二：

构造环形链表

把其中一个链表的头尾相连，对另一个链表采用快慢指针。如果这两个链表相交，两个快慢指针一定能够相遇，之后再采用Floyd算法，找到相交点。否则其中任意一个指针到达null，说明不存在相交的情况。

解法三：

观察上图例子可知，两个链表长度不相等，并且相交，那么，在交点之前的长度差就是abs(l1.length - l2.length)和两个完整的链表长度差是一致的。因为从交点之后两个链表的长度就一致了。

那么，就可以先遍历2次分别求出两个链表的长度，记为l1，l2.

使用两个指针，p1，p2.p1指向l1的首部，p2指向l2的首部。如果l1 > l2的话，p1先前移(l1-l2)个节点，然后p1，p2同时一步一步移动。

如果期间两个指针指向的链表节点相等（非null），则该节点就是交点，否则，不存在交点。

解法四：

同时遍历链表A和B，如果A到达链表尾，赋值B链表的头，继续遍历。B到达链表尾赋值A的头，继续遍历。无论相交与否，两者都会在null或者相交的交点处相遇。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        
        if (null == a || null == b) {
        	return null;
        }
        
        while (a != b) {
        	if (null == a) {
        		a = headB;
        	} else {
        		a = a.next;
        	}
        	
        	if (null == b) {
        		b = headA;
        	} else {
        		b = b.next;
        	}
        }
        return a;
    }
0%