写一算法求带头结点的单链表L的长度
时间: 2024-05-11 15:13:45 浏览: 13
1. 初始化计数器count为0,指针p指向头结点L->next。
2. 当p不为空时,执行以下步骤:
a. 计数器count加1。
b. 将p指向下一个节点p->next。
3. 返回计数器count的值,即为链表L的长度。
算法实现:
```
int getLength(ListNode* L) {
int count = 0;
ListNode* p = L->next;
while (p != NULL) {
count++;
p = p->next;
}
return count;
}
```
其中,ListNode为链表节点的结构体,包含数据域和指针域。头结点L为一个不存储数据的节点,其指针域指向链表的第一个节点。
相关问题
试写一算法求带头结点的单链表L的长度。
可以使用以下算法求带头结点的单链表L的长度:
1. 初始化计数器count为0,指针p指向L的头结点。
2. 如果p所指的结点不为空,将count加1。
3. 将p指向下一个节点。
4. 重复步骤2-3,直到p所指的结点为空。
5. 返回计数器count,即L的长度。
以下是使用C语言实现该算法的代码:
int getLength(ListNode *head) {
int count = 0;
ListNode *p = head->next;
while(p) {
count++;
p = p->next;
}
return count;
}
其中ListNode结构体表示单链表的节点:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
试写一算法对带头结点的单链表实现就地逆置。
以下是实现就地逆置的算法:
```c
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* prev = head->next;
ListNode* cur = prev->next;
while (cur != NULL) {
prev->next = cur->next;
cur->next = head->next;
head->next = cur;
cur = prev->next;
}
}
```
这个算法的时间复杂度是 O(n),其中 n 是链表的长度。