(LeetCode系列)刷题记

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

前言

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

  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
}

两个全排列的题目

第一道题

ZWdEW0

golang刷回溯遇到的坑

情况说明今天在做LeetCode-46题,DFS深搜写完,最后结果愣是不对,中途调试发现每次满足结束递归条件时得到的结果都是对的,但是后面一有满足条件就会造成最终的结果不对。 下面是46题的错误代码,中途调试打印cur可以正确打印,但是打印ret每次都会改变 1234567891011121314151617181920212223242526272829303132333435363738...

(LeetCode系列)242字母易位词

字母易位词,指的是两个单词只是字母的排列顺序不同,换言之就是字母的种类数以及字母出现的次数都一致 我们重点只需要验证 字母出现的次数以及字母的种类数是否一致 排序 sorted() 不会改变传入可迭代对象的顺序,而是返回一个排好序的可迭代对象 12def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sor...

(LeetCode系列)7整数反转

题意仔细审题,两个关键点 32位有符号整数,需要考虑负数如何处理 题中给的注意,考虑是否溢出 解法一:逆序累加我们将负数乘以-1,与正数统一处理,之后计算反转的结果之后再确认是否需要乘以-1 报错的代码 123456# 第一次提交:报错,错误测试用例,输入的内容经过反转之后超出了32位有符号整数的边界 def reverse(self, x: int) -> int: ...

(LeetCode系列)刷题记

两数相加思路: 分别求出两个链表都有数字时各个数字的和, 如果产生进位,将进位记录在计算下一位的时候加上 如果没有产生进位,移动到下一位 如果有链表为空,那么直接计算剩余链表的数字 与 进位的和 直到最后两个链表都为空,但是还有进位,此时我们还要再给进位分配一个链表的节点 求公共链表之后单独求不为空的链表的解法123456789101112131415def addTwoNumber...

(LeetCode系列)118杨辉三角

解法解法一(自己的解法,蛮力求解,找关系)发现每一行如果大于2个元素两边都用1填充,并且其他位置的元素的关系式如下: ele[i][j] = ele[i-1][j-1] + ele[i-1][j] ele[i][j] = 1 当且仅当j=0或j=i时 12345678910111213141516class Solution: def generate(self, numRow...

(LeetCode系列)191位1的个数

解决方法方法一:一位一位判断 我们对输入的数字从最后一位开始,每次和1进行与运算,之后每次左移1位 为什么每次不右移1位呢? 因为如果对于有符号整数,每次右移我们前面会填充符号位(正数填0负数填1)因此对于后面的计数会有影响,而左移对于有符号整数都只是在右边填充0 区分逻辑右移,逻辑左移与算数右移,算数左移: 逻辑左移=算数左移,右边统一添0 逻辑右移,左边统一添0 算数右移,左...

(LeetCode系列)136只出现一次的数字

解法解法一:暴力每次遍历一个数与后面的数进行比较,如果相等,则此次遍历break,开始遍历下一个数字。 时间复杂度:o(n^2) 空间复杂度:o(n) 解法二:排序时间复杂度:o(nlog2n) 空间复杂度:o(1) 解法三:使用hash表统计出现的次数时间复杂度:o(n) 空间复杂度:o(n) 解法四:使用集合统计出现一次的数字 定义一个新的集合,遍历题中给的数组,第一次出现的数字...