给定两个单向链表(长度分别为M,N),链表的尾部有部分重合(长度为S),找到重合的部分,输出重合的部分,和重合部分在两个链表中的位置。
时间: 2023-07-14 08:13:24 浏览: 92
我们可以先求出两个链表的长度差d,然后让指向较长链表的指针先走d步,然后两个指针同时走,当它们相遇时,就是重合的位置。代码实现如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_intersect(head1: ListNode, head2: ListNode) -> (ListNode, int, int):
"""
寻找两个链表的重合部分
:param head1: 链表1的头节点
:param head2: 链表2的头节点
:return: 重合部分的头节点,链表1和链表2中重合部分的起始位置
"""
if not head1 or not head2:
return None, -1, -1
# 计算链表1的长度
cur = head1
len1 = 0
while cur:
len1 += 1
cur = cur.next
# 计算链表2的长度
cur = head2
len2 = 0
while cur:
len2 += 1
cur = cur.next
# 让cur1指向较长的链表,cur2指向较短的链表
cur1, cur2 = head1, head2
if len1 < len2:
cur1, cur2 = cur2, cur1
len1, len2 = len2, len1
# cur1先走d步
d = len1 - len2
while d > 0:
cur1 = cur1.next
d -= 1
# cur1和cur2同时走,直到相遇
while cur1 and cur2 and cur1 != cur2:
cur1 = cur1.next
cur2 = cur2.next
if not cur1 or not cur2:
return None, -1, -1
# 返回重合部分的头节点,以及链表1和链表2中重合部分的起始位置
return cur1, len1 - (len1 - len2 + 1), len2 - 1
```
我们可以用以下代码进行测试:
```python
# 构造两个链表
head1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
head2 = ListNode(7, ListNode(8))
p1 = ListNode(5, ListNode(6))
p2 = ListNode(9, ListNode(10))
head1.next.next.next.next = p1
head2.next.next = p1
p1.next.next = p2
# 寻找重合部分
intersect_node, pos1, pos2 = find_intersect(head1, head2)
# 输出结果
if intersect_node:
print("重合部分的头节点为:", intersect_node.val)
print("在链表1中的起始位置为:", pos1)
print("在链表2中的起始位置为:", pos2)
else:
print("链表没有重合部分!")
```
输出结果为:
```
重合部分的头节点为: 5
在链表1中的起始位置为: 2
在链表2中的起始位置为: 0
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)