By

文章目录
  1. 1. 单向链表的结构
  2. 2. 单向链表是否有环
  3. 3. 判断两个单向链表是否相交
  4. 4. 判断两个相交的链表的交点1
  5. 5. 判断两个相交的链表的交点2
  6. 6. 演示结果代码

单向链表的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Link{
	public int data;
	public Link next;
	
	public Link(int data)
	{
		this.data=data;
	}
	
	//为了打印方便而加上去的。。
	public String toString()
	{
		return String.format("data:%s",this.data);
	}
}

单向链表是否有环

这题的思路很简单，先创建两个指针都指向链表的头部，一个fast指针每次走两步，另一个slow指针每次都走一步，如果fast指针能走到null的地方就说明该单链表没有环，否则fast和slow节点一定会走到同一个节点，表示有环

具体代码如下：

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
/**
 * 判断是否有环
 * @param head
 * @return
 */
public static boolean isCycle(Link head)
{
	boolean flag=false;
	if(head!=null)
	{
		Link fast=head,slow=head;
		while(fast!=null && fast.next!=null)//如果走到尾的肯定是fast先 所以这里只需要判断fast即可
		{
			slow=slow.next;
			fast=fast.next.next;
			if(fast==slow)
			{
				//两个指针指向了同一个节点 表示有环
				flag=true;
				break;
			}
		}
	}
	
	return flag;
}

判断两个单向链表是否相交

这里可以想一下，单向链表的相交是什么情况？
那肯定是一个Y字形的，因为两个链表都是单向的嘛^_^，所以有两种解法

  1. 利用上面的环，先遍历其中一个链表，另其首尾相连，（其实如果相交就会构成一个含有环的单链表），此时再从另一个链表的头部出发找是否有环就可以了
  2. 将两个链表都遍历到尾结果，如果这两个尾节点是同一个节点，说明就是相交

其实还可以使用hash的方法，也就是遍历两个链表进行hash，同一个节点的hash值肯定是一样的，然后就是两个集合的包含元素查找即可

判断两个相交的链表的交点1

其实这里根据上一问可知，如果有交点，那个交点就是环的入口点，所以先根据环的方法找入口点，然后将fast指针指向链表的头部，但是这个fast节点之后都是走一步，和slow同时走，它们相等的地方就是环的交点

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
48
/**
 * 两个链表是否相交  就是Y形状
 * @param head
 * @return //如果相交 返回交点
 */
public static Link isY(Link head1,Link head2)
{
	Link y=null;
	if(head1!=null && head2!=null)
	{
		Link h=head1;
		while(h.next!=null)
			h=h.next;
		h.next=head1;//将链表1的收尾相连
		
		boolean flag=false;
		if(head2!=null)
		{
			Link fast=head2,slow=head2;
			while(fast!=null && fast.next!=null)
			{
				slow=slow.next;
				fast=fast.next.next;
				if(fast==slow)
				{
					//两个指针指向了同一个节点 表示有环
					flag=true;
					break;
				}
			}
			
			if(flag)
			{
				fast=head2;//回到起点
				while(slow!=fast)
				{
					slow=slow.next;
					fast=fast.next;
				}
				y=fast;//得到交点
			}
			
		}
		h.next=null;//将第一个链表该为单链表
	}
	
	return y;
}

ps.如果需要看交点具体的推导看http://www.cnblogs.com/BeyondAnyTime/archive/2012/07/06/2580026.html

判断两个相交的链表的交点2

求出两个单链表的尾节点，在这个过程中可以很容易得到两个链表的长度，len1,len2，然后先让长的链表走abs(len1-len2)，然后让两个链表齐头并进就可以找到交点，复杂度是O(n+m)

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
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 两个链表是否相交  就是Y形状
 * 首先首先将两个环各自走到尾部，记录tail1和len1，以及tail2和len2
 * 如果tail1=tail2  则相交
 * 然后先让长的链表走abs(len1-len2)，然后让两个链表齐头并进就可以找到交点，复杂度是O(n+m)
 * @param head1
 * @param head2
 * @return
 */
public static Link isY2(Link head1,Link head2){
	Link y=null;
	if(head1!=null && head2!=null){
		Link tail1=head1,tail2=head2;
		int len1=1,len2=1;
		
		//记录两个链表的尾部节点 以及他们的长度
		while(tail1.next!=null)
		{
			len1++;
			tail1=tail1.next;
		}
		
		while(tail2.next!=null)
		{
			len2++;
			tail2=tail2.next;
		}
		
		//两个尾部相等就表示相交
		if(tail1==tail2)
		{
			//区分长链表和端链表
			Link longLink=head1,shortLink=head2;
			if(len1<len2)
			{
				longLink=head2;
				shortLink=head1;
			}
			
			//将长链表先走abs(len1-len2)步
			int diff=Math.abs(len1-len2);
			while(diff>0)
			{
				longLink=longLink.next;
				diff--;
			}
			
			while(longLink!=shortLink)
			{
				longLink=longLink.next;
				shortLink=shortLink.next;
			}
			
			y=longLink;
		}
	}
	
	return y;
}

演示结果代码

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
public static void main(String[] args)
{
	Link head1=new Link(1);
	Link link1=new Link(2);
	head1.next=link1;
	Link link2=new Link(3);
	link1.next=link2;
	Link link3=new Link(4);
	link2.next=link3;
	Link link4=new Link(5);
	link3.next=link4;
	Link link5=new Link(6);
	link4.next=link5;
	
	
	System.out.println(isCycle(head1));
	link5.next=link2;//使链表相交
	System.out.println(isCycle(head1));
	link5.next=null;//重置为单链表
	
	Link head2=new Link(7);
	Link link6=new Link(8);
	head2.next=link6;
	Link link7=new Link(9);
	link6.next=link7;//新建一个单列表
	
	System.out.println(isY(head1,head2));
	link7.next=link2;//将第二的单链表的某个元素指向第一个链表
	System.out.println(isY(head1,head2));
	
}

具体结果

false
true
null
data:3

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 单向链表的结构
  2. 2. 单向链表是否有环
  3. 3. 判断两个单向链表是否相交
  4. 4. 判断两个相交的链表的交点1
  5. 5. 判断两个相交的链表的交点2
  6. 6. 演示结果代码