彻底解决解决两个链表相交的问题

前言

两个链表相交涉及到关于链表的一系列问题:其中包含了如下子问题,并且涉及到了大量的算法思想,比如快慢指针

  1. 判断链表是否有环
  2. 链表有环的情况下找到环的入口节点
  3. 判断两个链表是否相交
  4. 相交的情况下找到相交时候的第一个节点

对应的7种情况

6aSs8P

解决代码

执行测试命令:go test -v intersection_test.go intersection.go -test.run TestIntersection

解决代码

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
package InterviewCoding

/**
* @Author: yirufeng
* @Date: 2021/11/25 8:21 上午
* @Email: yirufeng@foxmail.com
* @GitHub: https://www.github.com/sivanWu0222
* @Desc:
**/

type LinkedListNode struct {
Val int
Next *LinkedListNode
}

/*
题目:返回两个链表相交的节点
步骤:
1. 明确题目中的意思,两个链表有无环,是否一定相交(如果不一定的话,我们需要判断是否相交,只有在相交的情况下我们才可以返回相交的第一个节点)
2. 分情况进行讨论:
2.1 有环
2.1.1 一定相交:
直接找到相交的节点即可
2.1.2 不一定相交:
首先判断是否相交
相交的时候,找到相交的第一个节点并返回
2.2 无环
2.2.1 一定相交:
2.2.2 不一定相交:
首先判断是否相交
相交的时候,找到相交的第一个节点并返回
2.3 1个有环1个无环,说明一定不会相交,直接返回Nil就可以了
*/

//返回两个链表的相交节点,如果不相交返回Nil,否则返回相交的第一个节点
func Intersection(l1, l2 *LinkedListNode) *LinkedListNode {
//如果有一个为空,直接说明不相交
if l1 == nil || l2 == nil {
return nil
}

//判断两个链表是否有环,如果有环就返回环的起始节点
startOfl1Ring, startOfl2Ring := startNodeOfRing(l1), startNodeOfRing(l2)
//如果1个有1个没有,说明白不相交,直接返回nil
if ((startOfl1Ring == nil) && (startOfl2Ring != nil)) || ((startOfl1Ring != nil) && (startOfl2Ring == nil)) {
return nil
}

var ret *LinkedListNode
if startOfl1Ring != nil { //如果有环
ret = findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring)
} else { //如果没有环:此时就转换为我们正常的题解了
ret = findIntersectionNodeWhenBothNoCycle(l1, l2)
}

return ret
}

//当两个链表都没有环的时候,找到两个链表的相交节点(可能相交,可能不相交)
//三种解法去找出第一个相交的节点
func findIntersectionNodeWhenBothNoCycle(l1, l2 *LinkedListNode) *LinkedListNode {
//1. 获得第1个链表第2个链表的长度以及各自链表的最后一个节点
l1Length, l2Length := 1, 1
l1LastNode, l2LastNode := l1, l2
for l1LastNode.Next != nil {
l1Length, l1LastNode = l1Length+1, l1LastNode.Next
}
for l2LastNode.Next != nil {
l2Length, l2LastNode = l2Length+1, l2LastNode.Next
}

//判断各自最后一个节点是否相等,如果不相等,说明不相交,直接返回nil
if l1LastNode != l2LastNode {
return nil
}

//先走长度差
l1LastNode, l2LastNode = l1, l2
if l1Length > l2Length {
for i := 0; i < l1Length-l2Length; i++ {
l1LastNode = l1LastNode.Next
}
} else {
for i := 0; i < l2Length-l1Length; i++ {
l2LastNode = l2LastNode.Next
}
}

//然后一起走,如果中途相等直接返回
for l1LastNode != l2LastNode {
l1LastNode, l2LastNode = l1LastNode.Next, l2LastNode.Next
}

return l1LastNode
}

//当两个链表都有环的时候,找到两个链表的相交节点(可能相交,可能不相交(各自有一个自己的环))
func findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring *LinkedListNode) *LinkedListNode {
//判断两个链表是否有环的时候我们可以找到链表有环时候环的第一个节点
//如果两个环的起始节点都相同,此时问题转变为l1的起始节点到自己拥有环的开始节点和l2的起始节点到自己拥有环的开始节点的第一个相交节点
if startOfl1Ring == startOfl2Ring {
l1Temp, l2Temp := l1, l2
//转变为求两个无环单链表的相交节点
var l1TempLength, l2TempLength int

for l1Temp != startOfl1Ring {
l1Temp, l1TempLength = l1Temp.Next, l1TempLength+1
}

for l2Temp != startOfl2Ring {
l2Temp, l2TempLength = l2Temp.Next, l2TempLength+1
}

//长的先走
if l1TempLength > l2TempLength {
for i := 0; i < l1TempLength-l2TempLength; i++ {
l1Temp = l1Temp.Next
}
} else {
for i := 0; i < l2TempLength-l1TempLength; i++ {
l2Temp = l2Temp.Next
}
}

//此时一起走
for l1Temp != l2Temp {
l1Temp, l2Temp = l1Temp.Next, l2Temp.Next
}
return l1Temp

} else { //如果两个环的起始节点不同,让其中一个环开始走,走到起始节点为止,如果中途会出现和另外一个环起始节点相同,说明相交,否则各自成环
l1Temp := startOfl1Ring.Next
for l1Temp != startOfl1Ring {
if l1Temp == startOfl2Ring {
return startOfl2Ring
}
l1Temp = l1Temp.Next
}
}

return nil
}

//返回链表是否有环,如果有的话直接返回true,否则返回false
func startNodeOfRing(head *LinkedListNode) *LinkedListNode {
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast, slow = fast.Next.Next, slow.Next
//说明此时相遇,表明有环
if fast == slow {
break
}
}

//这里是第二个注意点,这里不仅仅要判断fast是否为空,还要判断fast.Next是否为空,
//因为让链表停止上面for循环的有两个条件:1. fast为空 2. fast.Next为空
//判断一下是因为fast为空或者fast.Next为空还是fast==slow退出的
if fast == nil || fast.Next == nil {
return nil
}

//走到这里说明有环,此时让fast指向head,然后fast与slow每次都走一步,一起相遇的时候返回即可
fast = head
for fast != slow {
fast, slow = fast.Next, slow.Next
}
return fast
}

测试代码

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
package InterviewCoding

import (
"testing"
)

/**
* @Author: yirufeng
* @Date: 2021/11/25 11:05 上午
* @Email: yirufeng@foxmail.com
* @GitHub: https://www.github.com/sivanWu0222
* @Desc:
**/

//测试两个链表
func TestIntersection(t *testing.T) {
//模拟场景
//1.1 两个不带环且不相交的链表
l1, l2 := constructTwoLinkedListWithoutCycleAndNotIntersection()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}

//1.2 两个不带环但是相交的链表:LeetCode原题
//已修复,由于&&写成了||
l1, l2 = constructTwoLinkedListWithoutCycleButIntersection()
if Intersection(l1, l2) == nil {
t.Log(Intersection(l1, l2))
t.Fatalf("expect to have intersection node.")
}

//2. 1个链表有环,1个无环
l1, l2 = constructTwoLinkedListButOneHasCycle()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}
//3. 两个链表都有环
//3.1 两个链表都有环,但是两个链表的环都是各自的
l1, l2 = constructTwoLinkedBothHasOwnCycle()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}

//3.2.1 两个链表都有环,并且两个链表是相交的,且交点在进入环之前
//todo: 有问题
l1, l2 = constructTwoLinkedListBothHasCycleAndIntersection()
if Intersection(l1, l2) == nil {
t.Fatalf("expect to have intersection node.")
}
//3.2.2 两个链表都有环,并且两个链表是相交的,且交点在环上
l1, l2 = constructTwoLinkedListBothHasCycleAndIntersectionII()
if Intersection(l1, l2) == nil {
t.Fatalf("expect to have intersection node.")
}
}

//两个不带环但是相交的链表
func constructTwoLinkedListWithoutCycleButIntersection() (l1, l2 *LinkedListNode) {
node := &LinkedListNode{Val: 5}
l1, l2 = &LinkedListNode{Val: 3}, &LinkedListNode{Val: 4, Next: &LinkedListNode{Val: 6, Next: node}}
l1.Next, l2.Next = node, node
return l1, l2
}

//两个不带环且不相交的链表
func constructTwoLinkedListWithoutCycleAndNotIntersection() (l1, l2 *LinkedListNode) {
l1, l2 = &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 4}}, &LinkedListNode{Val: 5, Next: &LinkedListNode{Val: 6}}
return l1, l2
}

//构造两个链表1个有环1个无环
func constructTwoLinkedListButOneHasCycle() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
node.Next, node2.Next = node2, node
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表的环都是各自的
func constructTwoLinkedBothHasOwnCycle() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
node.Next, node2.Next = node2, node
node3, node4 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node3.Next, node4.Next = node4, node3
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: node3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表都是相交的且相交的起点位于环的入口之前
func constructTwoLinkedListBothHasCycleAndIntersection() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node.Next, node2.Next = node2, node
node3 := &LinkedListNode{Val: 6, Next: node}
l1, l2 = &LinkedListNode{Val: 1, Next: node3}, &LinkedListNode{Val: 3, Next: node3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表都是相交的且相交的起点位于环上
func constructTwoLinkedListBothHasCycleAndIntersectionII() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node.Next, node2.Next = node2, node
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 6, Next: node2}}
return l1, l2
}