题目描述:
给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。
给定两个链表的头结点head1和head2。请返回一个bool值代表它们是否相交。
链表中节点的类型设置如下:
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
思路:
1、首先判断是否有环,
判断是否有环的方法如下:
1 /**
2 * 判断链表是否有环
3 * 判断方法是设置两个指针最初均指向头结点,然后fast每次走2步,slow每次走1步,
4 * 如果链表没有环,则fast指针肯定先指向表尾的null
5 * 如果有环,则fast和slow肯定会相遇。然后第一次相遇后我们将fast指针重新指向头结点,
6 * 然后fast和slow每次都走一步直到第二次相遇,那么第二次相遇的节点即为入环的节点
7 * @param head
8 * @return 若有,则返回入环节点,否则,返回null
9 */
10 public ListNode judgeRing(ListNode head){
11 if(head == null){
12 return null ;
13 }
14 ListNode fast = head ;
15 ListNode slow = head ;
16
17 while(fast != null && fast.next != null){
18 fast = fast.next.next ;
19 slow = slow.next ;
20 if(fast == slow){
21 fast = head ;
22 while(fast != slow){
23 fast = fast.next ;
24 slow = slow.next ;
25 }
26 return slow ;
27 }
28 }
29 return null ;
30 }
有环时查找入环点的方法的证明过程如下:
当fast与slow相遇时,slow还没走完链表,而fast已经在环内循环了n圈了,假设slow在相遇前走了s步,则fast走了2s步,设环长为r,有2s=s+nr,即s=nr.
由上图可知a+x=s, x+y=r,而我们的目标是找到a的位置。设上图那个拱起的曲线的长度为y,有a+x=s=nr=(n-1)r+r=(n-1)r+y+x,则a=(n-1)r+y. 这个公式告诉我们,从链表头和相遇点分别设一个指针,每次各走一步,这两个指针必定相遇,且相遇的第一个点为环入口点。
2、无环单链表是否相交判断有多种方法:
方法3的代码如下:
1 /**
2 * 判断两个无环链表是否相交
3 * @param head1
4 * @param head2
5 * @return
6 */
7 public boolean judgeIntersectWithoutRing(ListNode head1,ListNode head2){
8 int len1 = calLen(head1) ;
9 int len2 = calLen(head2) ;
10 ListNode intsect = null ;
11 if(len1 > len2){
12 intsect = judge(head1,len1,head2,len2) ;
13 }else{
14 intsect = judge(head2,len2,head1,len1) ;
15 }
16 //判断相交的节点是否为null,返回结果
17 if(intsect != null){
18 return true ;
19 }else{
20 return false ;
21 }
22 }
23
24 /**
25 * 计算链表的长度并返回
26 * @return
27 */
28 private int calLen(ListNode head){
29 int len = 0;
30 while(head != null){
31 len++ ;
32 head = head.next ;
33 }
34
35 return len ;
36 }
37
38 /**
39 * 按长链表、短链表的顺序传入两个链表,然后进行判断
40 * 如果相交,则输出首次相交的节点,否则输出null
41 * @return
42 */
43 private ListNode judge(ListNode headLong,int lenLong,
44 ListNode headShort,int lenShort){
45 int gap = lenLong - lenShort ;
46 //将较长的链表移动到与短链表等长的位置
47 while(gap != 0){
48 headLong = headLong.next ;
49 }
50 //开始判断
51 while(headLong != null && headShort != null){
52 if(headLong == headShort){
53 return headShort ;
54 }else{
55 headLong = headLong.next ;
56 headShort = headShort.next ;
57 }
58 }
59
60 return null ;
61 }
3、有环单链表是否相交的判断方法:先比较两个链表的入环节点是否相等,若想等,则相交,若不想等,则从某个链表的入环节点开始循环一周,判断是否有节点等于另一个链表的入环节点,若等于,则相交,否则不相交。
这个有环链表的判断是在得到两个环的入环节点的基础上进行的,比较简单,就不放代码了。