datetime:2023-07-04 19:30
author:nzb
链表
哈希表的简单介绍
- 1）哈希表在使用层面上可以理解为一种集合结构
- 2）如果只有key，没有伴随数据value，可以使用HashSet结构（C++中叫unOrderedSet）
- 3）如果既有key，又有伴随数据value，可以使用HashMap结构（C++中叫UnOrderedMap）
- 4）有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
- 5）使用哈希表增（put）、删（remove）、改（put）和查（get）的操作，可以认为时间复杂度为
O(1)，但是常数时间比较大 - 6）放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
- 7）放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小
有序表的简单介绍
- 1）有序表在使用层面上可以理解为一种集合结构
- 2）如果只有key，没有伴随数据value，可以使用TreeSet结构（C++中叫OrderedSet）
- 3）如果既有key，又有伴随数据value，可以使用TreeMap结构（C++中叫orderedMap）
- 4）有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
- 5）有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
- 5）红黑树、AVL树、
size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同 - 6）放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
- 7）放入哈希表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小
- 8）不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度
有序算表的固定操作
- 1）
void put(K key, V value)：将一个（key，value）记录加入到表中，或者将key的记录更新成value。 - 2）
V get(K key)：根据给定的key，查询value并返回。 - 3）
void remove(K key)：移除key的记录。 - 4）
boolean containsKey(K key)：询问是否有关于key的记录。 - 5）
K firstKey()：返回所有键值的排序结果中，最左（最小）的那个。 - 6）
K lastKey()：返回所有键值的排序结果中，最右（最大）的那个。 - 7）
K floorKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的前一个。 - 8）
K ceilingKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的后一个。
以上所有操作时间复杂度都是O(logN)，N为有序表含有的记录数有关有序表的原理，将在提升班“有序表详解”一章中讲叙原理
单双链表节点结构
// 定义节点结构c++
template <typename T>
struct Node {
T data; // 数据
Node* next; // 指向下一个节点的指针
// 构造函数
Node(T val) : data(val), next(nullptr) {}
};
// python
class Node:
def __init__(self, data):
self.data = data
self.next = None
由以上结构的节点依次连接起来所形成的链叫单链表结构。
// 定义节点结构c++
template <typename T>
struct Node {
T data; // 数据
Node* next; // 指向下一个节点的指针
Node* prev; // 指向前一个节点的指针
// 构造函数
Node(T val) : data(val), next(nullptr), prev(nullptr) {}
};
// python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
由以上结构的节点依次连接起来所形成的链叫双链表结构。
面试时链表解题的方法论
- 1）对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
- 2）对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
- 重要技巧：
- 1）额外数据结构记录（哈希表等）
- 2）快慢指针
反转单向和双向链表
- 【题目】 分别实现反转单向链表和反转双向链表的函数
【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)
单链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_linked_list(head: Node):
prev = None
cur = head
while cur is not None:
next_node = cur.next
cur.next = prev
prev = cur
cur = next_node
return prev
# 主函数
if __name__ == "__main__":
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head = reverse_linked_list(head)
- 双链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def reverse_doubly_linked_list(head: Node):
tmp = None
cur = head
while cur is not None:
next_node = cur.next
cur.next = tmp
cur.prev = next_node
tmp = cur
cur = next_node
return tmp
# 主函数
if __name__ == "__main__":
head = Node(1)
head.next = Node(2)
head.next.prev = head
head.next.next = Node(3)
head.next.next.prev = head.next
head.next.next.next = Node(4)
head.next.next.next.prev = head.next.next
head = reverse_doubly_linked_list(head)
打印两个有序链表的公共部分
- 【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
- 【要求】 如果两个链表的长度之和为N，时间复杂度要求为
O(N)，额外空间复杂度要求为O(1)
class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_common_part(head1: Node, head2: Node):
while head1 is not None and head2 is not None:
# 谁小谁移动
if head1.data < head2.data:
head1 = head1.next
elif head1.data > head2.data:
head2 = head2.next
else: # 相等打印，共同移动
print(f"data->{head1.data}")
head1 = head1.next
head2 = head2.next
# 主函数
if __name__ == "__main__":
# 示例
# 创建两个有序链表
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(6)
head2 = Node(2)
head2.next = Node(4)
head2.next.next = Node(6)
head2.next.next.next = Node(8)
print("Common Part: ", end="")
print_common_part(head1, head2)
判断一个链表是否为回文结构
- 【题目】给定一个单链表的头节点head，请判断该链表是否为回文结构。
- 【例子】
1->2->1，返回true；1->2->2->1，返回true；15->6->15，返回true；1->2->3，返回false。 【例子】如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
笔试：利用栈，遍历一遍依次放到栈里面，如何重新遍历链表，遍历一个，栈弹出一个，对比一样不一样，知道遍历结束
- 面试：快慢指针，一定到自己coding
- 快指针走到终点的时候，慢指针来到中点位置，头和尾用一个引用记住
- 中点往下遍历的时候，逆序，慢指针指向空
- 头和尾同时往中间走，每一步比对，任何一个走到空停
- 返回结果之前，把后半部分逆序回去，再返回是否回文
快一次走两步，慢针一次走一步，这件事儿你一定要自己去coding，为啥呢？ 因为根据实际题目出现的需求，有可能快慢指针是需要做定制的，比如说我有一种需求，是12321，当奇数的时候，我希望快指针走完的时候，慢指针正好压中唯一的终点。123321，我如果是偶数个，我希望快指针在走完的时候，慢指针压中的是终点中的前一个。那么这样一种情况我就需要根据长度为奇数和长度为偶数去分析它写出正确的算法没错吧？
如果另外一道题目，它跟你说的是，我希望在奇数个的时候，我的快指针走完的时候慢指针来到唯一终点的位置，但是如果我是偶数个，我希望在我快指针走完的时候，慢指针来到的是终点的下一个终点的位置， 那你会知道，如果这道题目它的需求是这个的话，你的逻辑会有小的不同， 这只是边界条件而已，它跟算法无关，那么你必须通过自己coding的方式把它写熟了，
还有一种例子是这样的，比如说我做这样一种定制就是 我在奇数个的时候，我总是希望我的快指针走完的时候，我慢针来到终点的前一个点的位置。 而我偶数个的时候呢，我希望快指针走完的时候，慢指针能来到我前一个终点的 再前一个位置， 他只是慢指针提前走个一两步或者快指针提前走个一两步就可以完成这样的小的差别的定制
但是你必须把它写熟，因为如果你在面市场，或者在笔试的过程中卡住， 你可能要卡很久，所以你在线下先把它给写熟了， 尤其是链表长度为一个的时候，链表长度为两个的时候，链表长度为三个的时候很特殊的小数据情况下， 你也得对。
class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_node(node: Node, double=False):
while node:
if double:
print(f"({node.prev.data if node.prev else None}){node.data}", end="->")
else:
print(node.data, end="->")
node = node.next
# 笔试
# def is_palindrome(head: Node):
# stack = []
# cur = head
# while cur is not None:
# stack.append(cur.data)
# cur = cur.next
# while head:
# if head.data != stack.pop():
# return False
# head = head.next
# return True
# 面试
def is_palindrome(head: Node):
"""
偶数：1->2->3->2->2->1->None，走完快指针指向空，慢指针指向第二个2，从慢指针开始反转
奇数：1->2->3->2->1->None，走完快指针指向最后一个1，慢指针指向3(中点)，从慢指针开始反转
:param head:
:return:
"""
def reverse_list(head2: Node):
prev = None
cur = head2
while cur:
next = cur.next
cur.next = prev
prev = cur
cur = next
return prev
if not head:
return True
slow, fast, prev_slow = head, head, head
# 使用快慢指针找到链表中点
while fast and fast.next:
prev_slow = slow
slow = slow.next # mid
fast = fast.next.next # end
# 反转后半部分链表
second_half = reverse_list(slow)
# 比较前半部分和反转后的后半部分是否相等
first, cur = head, second_half
while cur:
if cur.data != first.data:
# 复原链表
prev_slow.next = reverse_list(second_half)
print(print_node(head), end=" ")
return False
first = first.next
cur = cur.next
# 复原链表
prev_slow.next = reverse_list(second_half)
print(print_node(head), end=" ")
return True
# 主函数
if __name__ == "__main__":
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(2)
head.next.next.next.next.next = Node(1)
print("偶数不是回文，Is Palindrome:", is_palindrome(head), end="\n")
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(3)
head.next.next.next.next = Node(2)
head.next.next.next.next.next = Node(1)
print("偶数是回文，Is Palindrome:", is_palindrome(head), end="\n")
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(1)
head.next.next.next.next = Node(2)
print("奇数不是回文，Is Palindrome:", is_palindrome(head), end="\n")
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(1)
print("奇数是回文，Is Palindrome:", is_palindrome(head), end="\n")
print("\n----------is_palindrome-------------")
# 1->2->3->2->2->1->None 偶数不是回文，Is Palindrome: False
# 1->2->3->3->2->1->None 偶数是回文，Is Palindrome: True
# 1->2->3->1->2->None 奇数不是回文，Is Palindrome: False
# 1->2->3->2->1->None 奇数是回文，Is Palindrome: True
def middle_step(head):
"""
快指针走完，慢指针到想要的位置
1、链表长度为奇数时，快指针走完在最后节点
2、链表长度未偶数时，快指针走完为空
:param head:
:return:
"""
if not head:
return None
if not head.next: # 1个节点
return head
slow, fast, prev_slow, prev_prev_slow = head, head, head, head
while fast and fast.next:
prev_prev_slow = prev_slow # 注意这行和下一行的顺序，先这行
prev_slow = slow
slow = slow.next
fast = fast.next.next
if fast: # 奇数
print(f"奇数中点位置：{slow.data}")
print(f"奇数中点前一个位置：{prev_slow.data}")
else: # 偶数
print(f"偶数中点前一个位置：{prev_slow.data}")
print(f"偶数中点前一个再前一个位置：{prev_prev_slow.data}")
print(f"偶数中点下一个位置：{slow.next.data if slow.next else None}") # 2个节点
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)
print(print_node(head))
middle_step(head)
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print(print_node(head))
middle_step(head)
# 1->2->3->4->5->6->None
# 偶数前一个：3
# 偶数后一个:5
# 偶数前前一个:2
# 1->2->3->4->5->None
# 奇数前一个：2
# 奇数后一个:4
# 奇数前前一个:1
将单向链表按某值划分成左边小、中间相等、右边大的形式
- 【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
- 【进阶】在实现原问题功能的基础上增加如下的要求
- 【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
- 【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样
- 【要求】调整后所有大于pivot的节点之间的相对顺序和调整前一样
【要求】时间复杂度请达到
O(N)，额外空间复杂度请达到O(1)。笔试方法：申请一个列表，遍历链表，把每个节点放进去，归并排序，然后遍历一个一个链接起来
- 面试方法：
class Node:
def __init__(self, data):
self.data = data
self.next = None
def adjust_linked_list(head: Node, pivot: int) -> Node:
lt_head = lt_tail = None
eq_head = eq_tail = None
gt_head = gt_tail = None
cur = head
# 分别将节点连接到对应的链表上
while cur is not None:
next_node = cur.next
# 必须设置下个节点为None，不然无限循环下去
cur.next = None
if cur.data < pivot:
if not lt_head:
lt_head = lt_tail = cur
else:
lt_tail.next = cur
lt_tail = cur
elif cur.data == pivot:
if not eq_head:
eq_head = eq_tail = cur
else:
eq_tail.next = cur
eq_tail = cur
else:
if not gt_head:
gt_head = gt_tail = cur
else:
gt_tail.next = cur
gt_tail = cur
cur = next_node
# 将三个链表连接起来
if lt_tail:
lt_tail.next = eq_head
if eq_tail is None:
# 如果没有相等的节点，需要把相等的尾指到小于的尾，否则连不上大于区域
eq_tail = lt_tail
if eq_tail:
eq_tail.next = gt_head
return lt_head if lt_head else (eq_head if eq_head else gt_head)
# return lt_head if lt_head is not None else (eq_head if eq_head is not None else gt_head)
# 打印链表
def display_linked_list(head: Node):
current = head
while current is not None:
print(current.data, end=" ")
current = current.next
print()
if __name__ == "__main__":
# 示例
# 创建链表：1 -> 4 -> 3 -> 2 -> 5 -> 2
head = Node(1)
head.next = Node(4)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(2)
print("Original linked list:")
display_linked_list(head)
pivot_value = 3
new_head = adjust_linked_list(head, pivot_value)
print(f"After adjusting with pivot {pivot_value}:")
display_linked_list(new_head)
复制含有随机指针节点的链表
- 【题目】一种特殊的单链表节点类描述如下
- rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
- 【要求】时间复杂度
O(N)，额外空间复杂度O(1)
class Node:
def __init__(self, data, next=None, rand=None):
self.data = data
self.next = next
self.rand = rand
# 笔试（使用哈希表（字典））
def copy_linked_list_with_random_pointer_dict(head: Node):
tmp = {}
cur = head
while cur is not None:
tmp[cur] = Node(cur.data)
cur = cur.next
cur = head
while cur is not None:
tmp.get(cur).next = tmp.get(cur.next)
tmp.get(cur).rand = tmp.get(cur.rand)
cur = cur.next
return tmp.get(head)
# 面试
def copy_linked_list_with_random_pointer(head: Node):
if head is None:
return None
# 复制节点
cur = head
while cur:
next_node = cur.next
cur.next = Node(cur.data)
# 复制的节点的下一个节点就是，原始节点的下一个节点
cur.next.next = next_node
cur = next_node
# 处理random节点
cur = head
while cur:
if cur.rand:
cur.next.rand = cur.rand.next
cur = cur.next.next
# 分割(画个简易图容易理解)
new_head = head.next
cur = head
# print(print_node(head))
while cur:
next_node = cur.next # 可能是原始节点也可能是复制节点
cur.next = next_node.next if next_node else None
cur = next_node
# print(print_node(head))
# print(print_node(new_head))
return new_head
def display_linked_list(head):
current = head
while current:
rand_data = current.rand.data if current.rand else None
print(f"Data: {current.data}, Rand: {rand_data}")
current = current.next
def print_node(node: Node, double=False):
while node:
if double:
print(f"({node.prev.data if node.prev else None}){node.data}", end="->")
else:
print(node.data, end="->")
node = node.next
# 示例
# 创建链表：1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
# 设置随机指针
head.rand = head.next.next # 1 -> 3
head.next.rand = head.next.next.next.next # 2 -> 5
head.next.next.rand = head # 3 -> 1
head.next.next.next.rand = head.next.next # 4 -> 3
head.next.next.next.next.rand = head.next # 5 -> 2
print("Original linked list:")
display_linked_list(head)
# new_head = copy_linked_list_with_random_pointer_dict(head)
new_head = copy_linked_list_with_random_pointer(head)
print("Copied linked list:")
display_linked_list(new_head)
两个单链表相交的一系列问题
- 【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回
null - 【要求】如果两个链表长度之和为N，时间复杂度请达到
O(N)，额外空间复杂度请达到O(1)。
无环的链表一定会走到空，有环的一定不会，因为单链表只有一个next
- 笔试：使用集合，遍历链表，查看是否在集合里，不存在放入集合（注意是节点，不是值），存在当前节点就是入环节点
- 面试：快慢指针
- 第一步：判断链表有环无环，快指针和慢指针相遇的时候，快指针回到开头，然后再同时走，相等的时候就是入环节点
- 分类
- 链表1和链表2都无环
- 不相交：平行
- 相交，两条链表最后节点一定是公共节点
- 解决方法：
- 遍历链表1到最后一个节点记住
end1和length1 - 遍历链表2到最后一个节点记住
end2和length2 - 如果
end1和end2内存地址相同吗- 相同：相交，长链表先走长度差值
abs(length1 - length2)，然后一起走，这样两条链表一定会在相交节点相遇 - 不同：平行
- 相同：相交，长链表先走长度差值
- 遍历链表1到最后一个节点记住
- 其中一个链表有环，另一个无环，不可能相交，因为单链表只有一个next
- 两个都有环
- 各自成环，不想交，类似
66 - 1个入环节点，2个链表的入环节点是同一个
- 2个入环节点
- 解决方法(区分)：
- 第一步：如果
loop1==loop2就是第2种情况，然后如何求这种情况的相交节点，走无环链表的思路，跟有没有环没关系（相当于在入环节点切割，不看环的部分） - 第二步：让
loop1继续往下走，在转回自己之前，能遇到loop2就是情况3，返回loop1和loop2都行，否则就是情况1，不相交
- 第一步：如果
- 各自成环，不想交，类似
- 链表1和链表2都无环
2个都有环，1个入环节点
head1
\ head2
\ /
\/
|
|
|————|
| |
|————|
2个都有环，2个入环节点
head1 head2
\ /
\ /
|————|
| |
|————|
class Node:
def __init__(self, data, next=None, rand=None):
self.data = data
self.next = next
self.rand = rand
def get_loop_node(head: Node):
"""返回入环节点"""
if not head or not head.next:
return None
slow, fast = head.next, head.next.next # 快慢指针都走了一步
while slow != fast: # 相遇跳出
if not fast or not fast.next: # 快指针走完了，无环
return None
slow, fast = slow.next, fast.next.next
cur = head
while cur != slow:
slow, cur = slow.next, cur.next
return slow
def no_loop_linked_list(head1: Node, head2: Node):
"""2个链表都无环"""
cur1, cur2, n = head1, head2, 0
while cur1.next:
n += 1
cur1 = cur1.next
while cur2.next:
n -= 1
cur2 = cur2.next
if cur1 != cur2: # 最后一个节点不相等，一定不想交
return None
cur1, cur2 = (head1, head2) if n > 0 else (head2, head1) # cur1表示长链表， cur2表示短链表
n = abs(n)
# 长链表先走差值
while n > 0:
n -= 1
cur1 = cur1.next
while cur1 != cur2:
cur1, cur2 = cur1.next, cur2.next
return cur1
def both_loop_linked_list(head1: Node, loop1: Node, head2: Node, loop2: Node):
"""
2个链表都有环
3种情况
:param head1:
:param loop1:
:param head2:
:param loop2:
:return:
"""
# 第二种情况
if loop1 == loop2:
cur1, cur2, n = head1, head2, 0
while cur1 != loop1:
n += 1
cur1 = cur1.next
while cur2 != loop2:
n -= 1
cur2 = cur2.next
cur1, cur2 = (head1, head2) if n > 0 else (head2, head1)
n = abs(n)
while n > 0:
n -= 1
cur1 = cur1.next
while cur1 != cur2:
cur1, cur2 = cur2.next, cur2.next
return cur1
else:
cur1 = loop1.next
while cur1 != loop1:
# 第三种情况
if cur1 == loop2:
return loop1 # or loop2
cur1 = cur1.next
# 第1中情况，66
return None
def get_intersect_node(head1: Node, head2: Node):
if not head1 or not head2:
return None
loop1 = get_loop_node(head1)
loop2 = get_loop_node(head2)
if not loop1 and not loop2: # 2个都无环
return no_loop_linked_list(head1, head2)
elif loop1 and loop2: # 2个都有环
return both_loop_linked_list(head1, loop1, head2, loop2)
else: # 其中一个有环，一定不相交
return None
# 创建链表: 1 -> 2 -> 3 -> 4
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
# 创建链表: 1 -> 2 -> 3 -> 4
head2 = Node(1)
head2.next = Node(2)
head2.next.next = Node(3)
head2.next.next.next = Node(4)
print(f"2个无环平行{get_intersect_node(head1, head2)}")
# 创建链表: 1 -> 2 -> 3 -> 4 -> 5
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
head1.next.next.next.next = Node(5)
# 创建链表: 2 -> 1 -> 3 -> 4
head2 = Node(2)
head2.next = Node(1)
head2.next.next = head1.next.next
head2.next.next.next = head1.next.next.next
print(f"2个无环，相交的节点值：{get_intersect_node(head1, head2).data}")
# 创建链表: 1 -> 2 -> 3 -> 4 -> 3 (有环)
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
head1.next.next.next.next = head1.next.next
# 创建链表: 2 -> 1 -> 3 -> 4
head2 = Node(2)
head2.next = Node(1)
head2.next.next = Node(3)
head2.next.next.next = Node(4)
print(f"1个有环，1个无环，一定不相交：{get_intersect_node(head1, head2)}")
# 创建链表: 1 -> 2 -> 3 -> 4 -> 3 (有环)
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
head1.next.next.next.next = head1.next.next
# 创建链表: 2 -> 1 -> 3 -> 4 -> 1 (有环)
head2 = Node(2)
head2.next = Node(1)
head2.next.next = Node(3)
head2.next.next.next = Node(4)
head2.next.next.next = head2.next
print(f"2个都有环，第一种情况66：{get_intersect_node(head1, head2)}")
# 创建链表: 1 -> 2 -> 3 -> 4 -> 3 (有环)
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
head1.next.next.next.next = head1.next.next
# 创建链表: 5 -> 2 -> 3 -> 4 -> 3 (有环)
head2 = Node(5)
head2.next = head1.next
print(f"2个都有环，第二种情况1个入环节点，相交值：{get_intersect_node(head1, head2).data}")
# 创建链表: 1 -> 2 -> 3 -> 4 -> 2 (有环)
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
head1.next.next.next.next = head1.next
# 创建链表: 5 -> 4 -> 2 -> 3 -> 4 (有环)
head2 = Node(5)
head2.next = head1.next.next.next
print(f"2个都有环，第三种情况2个入环节点，相交值：{get_intersect_node(head1, head2).data}")