函数输出给定链表中的环的长度
时间: 2024-05-03 14:23:22 浏览: 16
以下是一个Python函数,它接受一个链表头作为输入,并返回链表中的环的长度(如果存在环的话):
```python
def find_loop_length(head):
slow = head
fast = head
# 寻找环中的相遇点
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if not fast or not fast.next:
# 没有环
return 0
# 计算环的长度
count = 1
fast = fast.next
while slow != fast:
fast = fast.next
count += 1
return count
```
该函数使用双指针法来检测链表中是否存在环,并找到环中的相遇点。然后,它使用一个辅助指针来计算环的长度。如果链表中不存在环,则函数返回0。
相关问题
c++函数输出给定链表中的环的长度
以下是C++代码实现,其中包括了判断链表是否有环的函数 isCycle 和计算环的长度的函数 cycleLength:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int isCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return 0;
}
ListNode *slow = head;
ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return 1;
}
}
return 0;
}
int cycleLength(ListNode *head) {
if (head == NULL || head->next == NULL) {
return 0;
}
ListNode *slow = head;
ListNode *fast = head;
int length = 0;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *p = slow;
do {
p = p->next;
length++;
} while (p != slow);
break;
}
}
return length;
}
int main() {
ListNode *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = head->next->next;
if (isCycle(head)) {
cout << "Cycle length is " << cycleLength(head) << endl;
} else {
cout << "No cycle in the linked list" << endl;
}
return 0;
}
```
python中比较两个链表的长度
要比较两个链表的长度,可以遍历链表并计数节点的数量。以下是一个示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def get_length(head):
length = 0
current = head
while current:
length += 1
current = current.next
return length
def compare_lists_length(list1, list2):
length1 = get_length(list1)
length2 = get_length(list2)
if length1 > length2:
return "List 1 is longer"
elif length1 < length2:
return "List 2 is longer"
else:
return "Both lists have the same length"
# 示例用法
# 创建链表 1: 1 -> 2 -> 3 -> None
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(3)
# 创建链表 2: 4 -> 5 -> None
list2 = ListNode(4)
list2.next = ListNode(5)
print(compare_lists_length(list1, list2)) # 输出 "List 1 is longer"
```
在上述示例中,我们定义了一个 `ListNode` 类来表示链表的节点。`get_length` 函数用于获取给定链表的长度。`compare_lists_length` 函数使用 `get_length` 函数来比较两个链表的长度,并返回相应的结果。最后,我们创建了两个示例链表并调用 `compare_lists_length` 函数进行比较。