算法67-链表相交问题

先看探索如何求一个链表存在环以及找出环的第一个节点问题

给出一个链表如下

用代码判断是否存在环，并找到环的第一个节点

方法1：

1 快慢指针，从头结点触发，快指针每次走两步，慢指针每次走一步

2若两个指针相遇，说明存在环，若不会相遇，最终走到nil’，则说明不存在环

3，若相遇，将快指针退回头节点，快指针也每次走一步，慢指针保持不变向前推进，快慢指针再次相遇的点就是环的第一个点

方法2：set方法，遍历一个链表麻将棋节点放进set，若放入时返回以存在，则说明有环，此方法也可以解决两个环是否相交的问题

再来探讨第二个问题。假如有两个链表，如何判断是否相交？

首先需要清楚的一点，两个链表相交后，从交点起，两个链表将共用一个链表，因为每个节点只有一下next指针，一个next指针就意味着不会再分叉

其次，我们来分析，通过上面单链表求环的第一个节点的函数，我们获得了两个链表的环的第一个节点loop1和loop2，那么有四种可能的情况

1 loop1和loop2都为空，这种情况下，可能会出现详见
2，loop1为空，loop2不为空
3，loop1不为空，loop2为空，2和3这两种情况不会出现相交，因为两个链表的tail都不是同一个节点
4，都不为空，可能相交，又可以细分为三种情况
4.1 都有环，但是不相交
4.2 共同拥有环，也就是交点是环的第一个节点或者之前
4.3 焦点在环上
如下：

4.1

4.2

4.3

代码：

函数1 确定链表是否有环，返回环环的第一个节点，没有则返回nil

方法：快慢指针，两个指针第一次相交后，快指针回到头结点，变为每次移动一步，快慢指针再次相遇的节点就是所求的节点

func getloopnode(head *LinkedNode) *LinkedNode{
	//快慢指针一定要先判断的基础，节点大于2个
	if head ==nil || head.next == nil || head.next.next == nil{//只有一个节点或两个节点时，返回头结点
		return nil
	}
	fast:=head
	slow:=head
	//移动款慢指针直到两个指针相交
	for  fast.next != nil && fast.next.next != nil {
		slow=slow.next
		fast=fast.next.next
		// fmt.Println(fast)
		//相交,快指针退回head，快指针每次移动一步，直到快慢指针再次相遇，返回相遇的节点
		if fast == slow{
			fast=head
			for fast.next != nil && slow.next != nil{
				fast=fast.next
				slow=slow.next
				if fast==slow{
					return fast
				}
			}
		}
	}
	return nil
}
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

函数2 两个链表都没环，求交点

方法， 先判断tail节点是否是同一个地址，是则说明相交，否则说明必定不相交，确定相交，然后从比较短的链表的头结点位置开始，两个链表以同样的位置开始遍历，知道遇到交点

//情况1  都无环
func noloop(head1,head2 *LinkedNode) *LinkedNode{
	tmp1:=head1
	tmp2:=head2
	n1,n2:=0,0
	for tmp1 !=nil{
		tmp1=tmp1.next
		n1++
	}
	for tmp2 !=nil{
		tmp2=tmp2.next
		n2++
	}
	if tmp1 != tmp2{
		return nil
	}
	fmt.Println(n1,n2)
	n:=int(math.Abs(float64(n1)-float64(n2)))
	var first *LinkedNode
	var second *LinkedNode

	if n1>n2{
		first=head1
		second=head2
	}else{
		first=head2
		second=head1
	}
	for n != 0{
		first=first.next
		n--
	}
	for first != second{
		first=first.next
		second=second.next

	}
	return first
}
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

函数3，都有环，对应上面情况4，得到两个链表的环的第一个节点之后，判断两个节点是否是同一个，是同一个就调用函数2，得到交点；不是同一个，则交点在环上或者不相交，此时令一个loop继续向前，走完一圈没有碰到另一个节点则说明不相交，否则返回交点

func bothloop(loop1,loop2,head1,head2 *LinkedNode)*LinkedNode{
	var tmp *LinkedNode
	//若两个链表的存在环，且环的第一个节点相等，要么所求的点就是loop1，要么在loop1之上
	//此时可以将loop1，loop2作为ail，去求无环部分时候有交点
	//实际上解决了4.1这个分支
	if loop1==loop2{
		tmp=noloop(head1,head2,loop1,loop2)
		if tmp== nil{//无交点返回loop1，说明咯op就是所要求的点
			return loop1
		}else{//有交点返回交点
			return tmp
		}
		//loop1 !=loop2 要么交点是环上的某一点，没要么就是不相交
		//判断交点是否是环上的某一点：loop1继续往前推进，走完环如果都没遇到loop2说明不想交，否则就返回相遇的点既是交点
	}else{
		loop:=loop1
		for loop != loop2{
			loop=loop.next
			if loop==loop1{//若loop循环一圈，未曾遇见loop2，说明不想交
				return nil
			}
		}
		return loop//loop1,loop2相遇，返回这个节点
	}

	return nil
}
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

整体代码：

package main

import (
	"fmt"
	"math"
	// "sort"
	// "time"
)

//链表本身，包含长度，头结点和尾节点，对于一个双向链表，
//我们只关注它的haea和tail，head和tail是一个个具体的节点(这里我将链表当做单向链表来用)
type LinkedList struct {
	len  int
	head *LinkedNode
	tail *LinkedNode
}
//链表中的一个节点的结构，包含节点的数据，前向指针，后向指针，指向的也是一个节点本身
type LinkedNode struct {
	data int
	next *LinkedNode
	prev  *LinkedNode
}
// type Data struct{
// 	key string
// 	data int
// }
//所有的操作都基于指针
func NewLinkedList() *LinkedList {
	return &LinkedList{
		len:  0,
		head: nil,
		tail: nil,
	}
}
//追加一个节点，链表没有头结点就把自己设为链表的头结点，头尾指针都指向自己
//有头结点就把自己放在最后，1先把自己的prev指向原来的tail，2把原来的tail的next指向自己，3把链表的tail设为自己
func (ll *LinkedList)Add(node *LinkedNode) {
	// node := &LinkedNode{
	// 	data: data,
	// }
	// fmt.Printf("hhhhhhead%v\n", ll.head)

	if ll.head==nil{
		ll.tail=node

		ll.head=node
	}else{
		// fmt.Printf("tttttail%v\n", ll.tail)
		node.prev=ll.tail

		ll.tail.next=node
		ll.tail=node
		
	}
	
	ll.len++//记得更新长度
}


func getloopnode(head *LinkedNode) *LinkedNode{
	//快慢指针一定要先判断的基础，节点大于2个
	if head ==nil || head.next == nil || head.next.next == nil{//只有一个节点或两个节点时，返回头结点
		return nil
	}
	fast:=head
	slow:=head
	//移动款慢指针直到两个指针相交
	for  fast.next != nil && fast.next.next != nil {
		slow=slow.next
		fast=fast.next.next
		// fmt.Println(fast)
		//相交,快指针退回head，快指针每次移动一步，直到快慢指针再次相遇，返回相遇的节点
		if fast == slow{
			fast=head
			for fast.next != nil && slow.next != nil{
				fast=fast.next
				slow=slow.next
				if fast==slow{
					return fast
				}
			}
		}
	}
	return nil
}
//情况1  都无环
//传参加上tail节点，func可以复用，可以指定从哪个节点（tail）向上检查交点
func noloop(head1,head2,tail1,tail2 *LinkedNode) *LinkedNode{
	tmp1:=head1
	tmp2:=head2
	n1,n2:=1,1
	for tmp1 !=tail1{
		tmp1=tmp1.next
		n1++
	}
	for tmp2 !=tail2{
		tmp2=tmp2.next
		n2++
	}
	if tmp1 != tmp2{
		return nil
	}
	fmt.Println(n1,n2)
	n:=int(math.Abs(float64(n1)-float64(n2)))
	var first *LinkedNode
	var second *LinkedNode

	if n1>n2{
		first=head1
		second=head2
	}else{
		first=head2
		second=head1
	}
	for n != 0{
		first=first.next
		n--
	}
	for first != second{
		first=first.next
		second=second.next

	}
	return first
}

func bothloop(loop1,loop2,head1,head2 *LinkedNode)*LinkedNode{
	var tmp *LinkedNode
	//若两个链表的存在环，且环的第一个节点相等，要么所求的点就是loop1，要么在loop1之上
	//此时可以将loop1，loop2作为ail，去求无环部分时候有交点
	//实际上解决了4.1这个分支
	if loop1==loop2{
		tmp=noloop(head1,head2,loop1,loop2)
		if tmp== nil{//无交点返回loop1，说明咯op就是所要求的点
			return loop1
		}else{//有交点返回交点
			return tmp
		}
		//loop1 !=loop2 要么交点是环上的某一点，没要么就是不相交
		//判断交点是否是环上的某一点：loop1继续往前推进，走完环如果都没遇到loop2说明不想交，否则就返回相遇的点既是交点
	}else{
		loop:=loop1
		for loop != loop2{
			loop=loop.next
			if loop==loop1{//若loop循环一圈，未曾遇见loop2，说明不想交
				return nil
			}
		}
		return loop//loop1,loop2相遇，返回这个节点
	}

	return nil
}
//先通过求环的func得到两个链表是否有环，根据结果分4种情况
//1，两个链表都无环，有可能出现相交的情况，找到两个链表的tail节点，如果是同一个指针则说明相交，否则不相交，
//2，一个有环，另一个无环
//3 同上，2和3不可能出现相交，因为两个链表的尾端都不是同一个节点，
//4，都有环，有可能相交

func FindfirstIntersectNode(head1,head2 *LinkedNode) *LinkedNode{
	if head1==nil && head2 ==nil{
		return nil
	}
	if head1.next==nil && head2.next==nil {
		if head1==head2{
			return head1

		}else{
			return nil
		} 
	}
	loop1:=getloopnode(head1)
	loop2:=getloopnode(head2)
	var internode *LinkedNode
	//情况1 都无环的情况，传入头结点和尾节点，去找交点
	if loop1 ==nil && loop2==nil{
		tail1:=gettail(head1)
		tail2:=gettail(head2)
		internode=noloop(head1,head2,tail1,tail2)
	}
	//情况2,2 一个有环  一个无环  都不可能相交  返回nil
	if (loop1 ==nil && loop2 != nil) || (loop2 ==nil && loop1 != nil) {
		return nil
	}
	//情况4，都有环
	if loop1 !=nil && loop2 != nil{
		internode=bothloop(loop1,loop2,head1,head2)
	}
	return internode
	}


func gettail(head *LinkedNode)*LinkedNode{
	for head!=nil{
		if head.next==nil{
			return head
		}else{
			head=head.next

		}
		
	}
	return head

}
func main(){
	var head LinkedNode
	head.data=18

	var l1 LinkedNode
	l1.data=5

	var l2 LinkedNode
	l2.data=20

    var l3 LinkedNode
	l3.data=4

    var l4 LinkedNode
    l4.data=3

	var l5 LinkedNode
    l5.data=8

	var l6 LinkedNode
    l6.data=12

	var l7 LinkedNode
	l7.data=15
	
	var head1 LinkedNode
	head1.data=9

	var ll2 LinkedNode
	ll2.data=22

	list := NewLinkedList()
	list.Add(&head)
	list.Add(&l1)
	list.Add(&l2)
	list.Add(&l3)
	list.Add(&l4)
	list.Add(&l5)
	list.Add(&l6)
	list.Add(&l7)


	list1 := NewLinkedList()
	list1.Add(&head1)
	list1.Add(&ll2)
	list1.Add(&l2)
	list1.Add(&l3)
	list1.Add(&l4)
	list1.Add(&l5)
	list1.Add(&l6)
	list1.Add(&l7)
	// l7.next=&l4
	// fmt.Println(getloopnode(&head))
	fmt.Println(noloop(&head,&head1,&l7,&l7))
	// fmt.Println(gettail(&head1))
}
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261