1.1. 题目
1.1.1. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
- 如果两个链表没有交点，返回 null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
1.1.2. 题解:
- 两条链表可能会相交!
- 对于示例的参数别看了. 跟题目没有关系的,只是为了解释测试用例的参数是啥意思而已!如果自己本地测试,用不着的!
1.1.3. 思路:
- 由于题目要求 时间复杂度是 O(n), 空间复杂度是 O(1),不然可以做用作弊法,就是把数据放到map里,然后看是否存在...
- 我第一反应的做法:
- 先分别算出A B 链表长度 aLen,bLen
- 如果 A比B长,那么让A先移动 aLen - bLen 步, 类似 示例1里,B先走,走到0位置,如果B比A长,一样做法,让长的先走 长多少步
- 然后 同时走,如果相同那么相交点了,如果走到nil,那么就是走到最后了!
- 算一下时间复杂度, 取长度
O(n) + O(n), 先移动|aLen - bLen|步, 时间复杂度也是O(n), 最后一起移动,时间复杂度也是O(n) - 那么时间复杂度是
4*O(n),所以符合条件,时间复杂度就是O(n),没有用额外空间,所以空间复杂度还是O(1)
- 另外一种思路:
- A和B同时走,当A走到末尾的时间,开始走B,同理,当B走到末尾的时候,开始走A, 那么如果相交,肯定会同时走到一个相同的点
- 为什么这么说呢, 看图中c1 是相交点, 假设 a1到c1的距离是x, b1到c1的距离是y,公共链表 c1到 c3 是 z
- A和B同时出发, 当A到达c3的时候,B还在 c3前面(y-x)的位置,然后 A开始走B的路线,等B到了末尾,开始走A的路线
- 因为第一次的时候, A比B到结尾c3快 (y-x),当第二圈的时候,A走的是B的距离,就慢了,慢了 (y-x),所以当第二圈的时候,B会在c1位置追上A
- 仔细想一下,就是 x + y + z = y + x + z,最开始相遇的点就是c1位置,因为c2,c3都是相遇的!只是最早的是 c1
- A和B同时走,当A走到末尾的时间,开始走B,同理,当B走到末尾的时候,开始走A, 那么如果相交,肯定会同时走到一个相同的点
1.1.4. 代码:
点击显示
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// 如果链表为空,直接返回
if headA == nil || headB == nil {
return nil
}
// 设置两个临时链表
nodeA := headA
nodeB := headB
// 定义两个参数,方便参考是否重新赋值了
var m,n int
for true {
// 如果相遇了,直接返回
if nodeA == nodeB {
return nodeA
}
// 两链表都移动一个节点
nodeA = nodeA.Next
nodeB = nodeB.Next
// 如果A节点走到了最后
if nodeA == nil {
if m == 0 {// 如果是第一次走到最后,把B赋值给A,且标记一下
nodeA = headB
m++
} else { // 如果不是第一次了,那么说明没有相遇,返回nil
return nil
}
}
// 如果B节点走到了最后
if nodeB == nil {
if n == 0 {// 如果是第一次走到最后,把A赋值给B,且标记一下
nodeB = headA
n++
} else { // 如果不是第一次了,那么说明没有相遇,返回nil
return nil
}
}
}
return nil
}
func getIntersectionNode2(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
// 分别取A和B的长度
aLen := nodeLen(headA)
bLen := nodeLen(headB)
if aLen > bLen {
// 如果A比B长,A先移动 a-b 长度的距离
for i:=0;i<aLen - bLen;i++ {
headA = headA.Next
}
} else {
// 如果B比A长, B先移动 b-a 长度的距离
for i:=0;i<bLen-aLen;i++ {
headB = headB.Next
}
}
// 遍历一个
for headA != nil {
// 如果相等,那么相遇了,返回
if headA == headB {
return headA
}
// 每次同时都移动一个节点
headA = headA.Next
headB = headB.Next
}
return nil
}
func nodeLen(head *ListNode) int {
var i int
for head != nil {
i++
head = head.Next
}
return i
}