两个单链表相交的一系列问题

单链表可能有环,也可能无环。给定两个单链表的头节点 head1 和 head2, 这两个链表可能相交,也可能不相交。
请实现一个函数,如果两个链表相交,请返回相交 的第一个节点;如果不相交,返回 null 即可。
要求:如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。

思路

本题目可以拆分为2大问题

  • 是否有环
  • 是否相交

然后又可以拆分为多个子问题

  • 判断单链表是否有环，如果有找出入环点
  • 两个无环链表是否相交
  • 两个有环链表是否相交
  • 一个有环链表和一个无环链表是否相交

判断单链表是否有环，如果有找出入环点

  • 快指针一次走两步，慢指针一次走一步，直到快慢指针相遇
  • 新指针从链表头开始走，慢指针从刚刚位置继续走
  • 新指针和慢指针相遇的地方就是入环点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 判断链表是否有环
	public static Node getLoopNode(Node head) {
		if(head == null || head.next ==null || head.next.next ==null){
			return null;
		}
		Node nq = head;
		Node ns = head.next.next;
		//循环使得快慢指针相遇
		while (ns != nq) {
			if(ns == null || nq == null){
				break;
			}
			ns = ns.next;
			nq = nq.next.next;
		}
		Node node = head;
		//新指针和慢指针遍历，直到相遇
		while (ns != node) {
			if(ns == null || node == null){
				return null;
			}
			node = node.next;
			ns = ns.next;
		}
		return node;
	}

两个无环链表是否相交

如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的

因此这两个链表的最后一个节点一定是公共的
所以先遍历两个链表，判断末尾节点是否是同一个，同时设置一个计数，表示两个链表长度的差值
然后让长的链表先从头走过这个差值，然后长短一起走，直到发现第一个公共节点

这个长度差值还可以体现在求链表倒数第k个结点。
即有2个指针指向链表，一个先走k步，然后两者一起走，直到有一个为空为止。
这样非空的指针指向的就是倒数k的节点
因为两者一个都相差k步，所有快的走完全程，慢的就停在了倒数k步上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 无环的时候找公共的节点
public static Node noLoop(Node head1, Node head2) {
	// n是记录长链表比短链表长多少，然后让长链表走过这一段，之后一起走，找到公共节点
	int n = 0;
	// head1走完全程
	Node n1 = head1;
	while (n1.next != null) {
		n++;
		n1 = n1.next;
	}
	// head2走完全程
	Node n2 = head2;
	while (n2.next != null) {
		n--;
		n2 = n2.next;
	}
	// 最后一个节点不相同，则一定没有公共节点
	if (n1 != n2) {
		return null;
	}
	// 把n1设置为长度更长的链表
	n1 = n > 0 ? head1 : head2;
	n2 = n1 == head1 ? head2 : head1;
	// n1把多出来的部分走过
	n = Math.abs(n);
	while (n != 0) {
		n--;
		n1 = n1.next;
	}
	// n1==n2时就是公共节点
	while (n1 != n2) {
		n1 = n1.next;
		n2 = n2.next;
	}
	return n1;
}

两个有环链表是否相交

  • 两个入环点相同
    说明相交点在环内，只需要判断一链表上俩指针相遇的那个节点，在不在另一条链表上

  • 两个入环点不同
    说明相交点不在环内，则类似于两个无环链表的遍历，只是遍历到入环点就停止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
	if (loop1 == loop2) {
		// 入环点相同，相交点在环外
		// 方法类似无环链表求公共点
		// 先求长度差，然后长的走过长度差，之后一起走，直到相遇
		int n = 0;
		Node n1 = head1;
		//遍历到入环点停止，而不是为空
		while (n1.next != loop1) {
			n++;
			n1 = n1.next;
		}
		Node n2 = head2;
		//遍历到入环点停止，而不是为空
		while (n2.next != loop2) {
			n--;
			n2 = n2.next;
		}
		n1 = n > 0 ? head1 : head2;
		n2 = n1 == head1 ? head2 : head1;
		n = Math.abs(n);
		//长的走过多余的部分
		while (n != 0) {
			n--;
			n1 = n1.next;
		}
		//一起走，直到相遇
		while (n1 != n2) {
			n1 = n1.next;
			n2 = n2.next;
		}
		return n1;
	} else {
		// 入环点不同，只要遍历一个环，检查另一个入环点是否在其中即可
		Node node = loop1;
		do {
			// loop2是否在loop1中
			if (node == loop2) {
				return node;
			}
			node = node.next;
		} while (node != loop1);
		// 不在其中，则不相交
		return null;
	}
}

一个有环链表和一个无环链表是否相交

一个有环链表和一个无环链表不可能相交

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static Node getIntersectNode(Node head1, Node head2) {
	if (head1 == null || head2 == null) {
		return null;
	}
	Node loop1 = getLoopNode(head1);
	Node loop2 = getLoopNode(head2);
	// 12都没有环
	if (loop1 == null && loop2 == null) {
		return noLoop(head1, head2);
	}
	// 12都有环
	if (loop1 != null && loop2 != null) {
		return bothLoop(head1, loop1, head2, loop2);
	}
	// 一个有环一个无环，不可能相交！
	return null;
}