pta6-2 求链式表的表长
时间: 2024-10-17 21:08:15 浏览: 7
pta6-2 题目通常是指某个编程题目,涉及到链表数据结构,这里的"求链式表的表长"指的是计算给定单向链表中节点的数量。在链表中,每个节点都有一个指向下一个节点的指针,所以要找到链表的长度,你需要从头开始遍历链表,直到遇到`null`(表示链表结束),计数器加一,最后返回计数器的值即为链表的长度。
这个过程可以使用递归或迭代的方式来实现。下面是基本的迭代算法示例:
```python
def getLinkedListLength(head):
if head is None:
return 0
else:
length = 1 # 初始化长度为1,因为已知有一个节点
current = head.next # 赋值当前节点为头节点的下一个节点
while current is not None:
length += 1
current = current.next
return length
# 或者使用递归版本
def getLinkedListLengthRecursive(head):
if head is None:
return 0
else:
return 1 + getLinkedListLengthRecursive(head.next)
```
这里假设`head`是链表的头节点,`head.next`是第二个节点,依此类推。
相关问题
pta 6-2 两个有序链表序列的合并
这道题可以采用归并排序的思想,把两个有序链表合并成一个有序链表。
具体实现步骤如下:
1. 定义一个新链表,用来存储合并后的结果。
2. 定义指针p和q分别指向两个有序链表的头结点,比较p和q指向的节点的大小,将较小的节点插入新链表中。
3. 如果p或q其中一个链表已经遍历完了,那么把另一个链表剩余的部分直接插入到新链表中。
4. 重复步骤2和步骤3,直到两个链表都遍历完毕。
5. 返回新链表的头结点。
C++代码如下:
```c++
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = (l1 ? l1 : l2);
return dummy->next;
}
```
pta2-3 链表去重c语言
pta2-3 链表去重通常是指在一个单链表中移除所有重复的节点,保持链表中元素唯一。在C语言中,你可以通过遍历链表并维护一个哈希集合(如`unordered_set`或`stdbool`数组)来完成这个任务。下面是基本的步骤:
1. 定义一个结构体表示链表节点,包含数据`data`和指向下一个节点的指针`next`。
```c
typedef struct Node {
int data;
struct Node* next;
} ListNode;
```
2. 创建一个辅助函数用于检查数据是否已存在于哈希集合中。这里我们可以使用`bool`类型的数组。
```c
bool isDuplicate(int data, bool hash[1000]) {
return hash[data];
}
```
3. 主函数中,初始化空链表和哈希集合,然后开始遍历链表。
```c
ListNode* removeDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
bool hash[1000] = {false};
ListNode* current = head;
while (current != NULL) {
if (!isDuplicate(current->data, hash)) {
hash[current->data] = true; // 添加当前节点到哈希集合
}
ListNode* temp = current->next;
if (temp != NULL && temp->data == current->data) {
// 如果找到重复项,删除它
current->next = temp->next;
} else {
current = temp;
}
}
return head;
}
```
4. 最后返回处理后的链表头节点。
阅读全文